시뮬레이션 알고리즘(백준 #1966)

---

Implementation / Simulation

시뮬레이션(Simulation) 알고리즘은 흔히 구현(Implementation) 알고리즘과 특별한 구분없이 쓰인다.

구현 알고리즘이란 문제를 봤을때 떠오르는 해결책은 단순한데 이를 코드로 구현하는 것의 복잡도가 높은 알고리즘을 말한다.

백준에서 시뮬레이션 문제로 구분되어있는 1966번 프린터 큐 문제를 통해 알아보고자 한다.

---

#1966 프린터 큐

우선 FIFO 기반인 큐를 통해 우선 순위를 부여하여 우선순위 큐와 같은 구현을 하고자 하는 문제이다.

# 3           -> 3번 테스트 할 것
# 1 0         -> 문서는 1개, 0번 인덱스 문서의 출력순서는?
# 5           -> 중요도 = 5
# 4 2         -> 문서는 4개, 2번 인덱스 문서의 출력순서는?
# 1 2 3 4     -> 중요도 = 1 2 3 4
# 6 0         -> 문서는 6개, 0번 인덱스 문서의 출력순서는?
# 1 1 9 1 1 1 -> 중요도 = 1 1 9 1 1 1

위와 같이 테스트 횟수가 주어지면 해당 횟수만큼 1회당 두줄에 거쳐서 문서수, 순서가 궁금한 문서의 인덱스 값,

각각 문서의 중요도가 주어진다.

 

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n):
    n,m = list(map(int, input().split( )))
    value = list(map(int, input().split( )))
    index = list(range(len(value)))
    index[m] = "target"

    # 순서 설정을 위한 변수 초기화
    order = 0
    
    while True:
        # value의 첫번째 값이 최댓값인 경우
        if value[0]==max(value):
            order += 1
                        
            # index의 첫번쨰 값이 target인 경우
            if index[0]=="target":
                print(order)    # 출력
                break
            # index의 첫번째 값이 target이 아닌 경우
            else:
                value.pop(0)    # value의 첫번째 값 pop
                index.pop(0)    # index의 첫번째 값 pop
        # 전부 해당이 안되는 경우 value와 index의 첫번째 값을 맨뒤로 보냄
        else: 
            value.append(value.pop(0))
            index.append(index.pop(0))

최우선 중요도의 값이 나타나면 target을 포함한 모든 원소의 order를 높여서 순위를 낮춰주고 target 값이 나타나기 전까지 최우선 중요도인 값을 제거한다. 최우선 중요도 값이 아닌 값이 맨 앞에 나타나면 pop(), append()를 연속으로 활용하여 맨앞의 값을 맨뒤로 보내는 과정을 반복하여 target값의 order를 결정하고 order는 출력 순서를 의미하므로 바로 출력해준다.

---