[Python] BOJ/백준 1966번 프린터 큐

[문제]

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

[풀이]

원하는 문서가 몇 번째로 인쇄되는지를 출력해야 하기 때문에 인쇄 큐 순서가 바뀔 때마다 인덱스 순서도 같이 바꿔줘야 한다. 그래야만 원래 m번째 문서가 언제 출력되는지 구할 수 있다.

 

입력값을 알맞게 변수에 넣은 후 idx 리스트를 선언한 후 원하는 문서 인덱스 값은 'target'으로 바꾼다.

예를 들어 예제 입력의 두 번째 테스트 케이스에서 idx[m] = 'target'을 하면 리스트 값을 [0, 1, 'target', 3]가 된다.

 

반복문의 범위는 importance 리스트의 길이이다.

변수 a에 importance 리스트 중 중요도가 가장 큰 값의 인덱스를 담는다.

그 후 리스트의 맨 앞 요소를 꺼낸 후 리스트의 마지막에 재배치하는 것을 a번 반복한다. 

인덱스 순서도 같이 변경해주어야 하기 때문에 idx 리스트도 위와 같이 재배치해준다.

리스트 순서를 재배치하는 반복문을 완료한 후에는 cnt를 1 증가시켜준다.

 

이 과정까지 거친 후에는 중요도가 가장 큰 문서가 리스트의 가장 앞에 위치한다.

만약 idx의 첫번째 원소가 'target'이라면 우리가 찾던 문서이기 때문에 cnt를 출력하고 break문을 통해 반복문을 탈출한다.

첫 번째 원소가 'target'이 아닐 경우, importance와 idx의 첫 번째 원소를 pop 해준다.

 

[코드]

import sys

if __name__ == '__main__':
    for _ in range(int(sys.stdin.readline())):
        n, m = map(int, sys.stdin.readline().split())
        importance = list(map(int, sys.stdin.readline().split()))
        idx = list(range(len(importance)))
        idx[m] = 'target'

        cnt = 0
        for __ in range(len(importance)):
            a = importance.index(max(importance))
            for j in range(a):
                importance.append(importance.pop(0))
                idx.append(idx.pop(0))
            cnt += 1

            if idx[0] == 'target':
                print(cnt)
                break
            else:
                importance.pop(0)
                idx.pop(0)