[백준] 1966번 : 프린터 큐 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1966번: 프린터 큐

 

1. 문제 설명

2. 풀이과정

해당 문제는 인쇄 차례를 구할 문서를 잘 쫓아가는 것이 핵심이다. 중요도가 동일한 문서가 존재할 수 있기 때문에 인쇄 차례를 구할 문서가 현재 어디에 위치하는지를 아는 것이 중요하다.

하여 처음 입력받는 인쇄 차례를 구할 문서의 위치를 계속 변경하며 해당 문서의 위치를 파악하도록 했다.

만약 제일 큰 중요도를 가진 문서를 출력할 때 그 문서가 찾고자 하는 문서라면 인쇄 순서를 출력하도록 구현했다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
3. 테스트 케이스의 개수를 입력받는다. T = int(sys.stdin.readline())
4. 테스트 케이스만큼 반복하며 for _ in range(T)
5. 문서의 개수와 인쇄 차례를 구할 문서의 위치를 입력받는다. N, M = map(int, sys.stdin.readline().split())
6. 문서의 중요도를 리스트로 입력받고 deque 자료구조로 저장한다. queue = deque(list(map(int, sys.stdin.readline().split())))
7. 인쇄 차례를 구할 문서가 몇 번째로 출력되는지 그 횟수를 저장할 변수를 생성하고 최솟값인 1로 저장한다. count = 1
8. 인쇄 차례를 구하면 멈추기 위해 일단 무한 반복문을 사용한다. while (True)
9. 만약 현재 저장된 중요도의 제일 앞 중요도가 전체 중요도 deque에서 제일 큰 값이라면 if (queue[0] == max(queue))
10. 해당 문서를 무조건 출력해야 하는데 이때 해당 문서가 인쇄 차례를 구할 문서라면 if (M == 0)
11. 인쇄 순서를 출력하고 print(count)
12. 인쇄 순서를 구했으므로 반복문을 종료한다. break
13. 반면 현재 인쇄할 문서가 구하려고 하는 문서가 아니면 else
14. 그냥 인쇄한다. queue.popleft()
15. 그리고 인쇄를 실행하였으므로 인쇄 횟수를 1 증가시킨다. count += 1
16. 반면에 현재 제일 앞 중요도가 전체 중요도 deque에서 제일 큰 값이 아니라면 else
17. 제일 앞 중요도를 제일 뒤로 옮긴다. queue.append(queue.popleft())
18. 매 반복 과정이 이루어질 때마다 인쇄 순서를 찾고자 하는 문서의 순서는 앞으로 당겨지는데 M -= 1
19. 만약 제일 앞 순서였다면 제일 뒤로 이동한다. if (M < 0): M = len(queue) - 1

반응형

3. 소스코드

import sys
from collections import deque

T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))

    count = 1
    while (True):
        if (queue[0] == max(queue)):
            if (M == 0):
                print(count)
                break
            else:
                queue.popleft()
                
            count += 1
        else:
            queue.append(queue.popleft())
        
        M -= 1
        if (M < 0):
            M = len(queue) - 1