[Baekjoon] 1966 - 프린터 큐

ivor·2023년 7월 1일

1966 Algorithms baekjoon python 구현 정렬

코딩테스트

목록 보기

9/10

[백준] 1966- 프린터 큐

문제 링크: https://www.acmicpc.net/problem/1966

코드

from collections import deque

test_cases = int(input())
while test_cases > 0:
    num_of_docu, idx = map(int,(input().split()))
    impts = list(map(int, input().split()))
    dq = deque(impts)
    count = 0
    
    while dq:    
        while dq[0] != max(dq):
            dq.rotate(-1)
            if idx <= 0:
                idx += len(dq)
            idx -= 1
        
        if idx == 0:
            dq.popleft()
            count += 1
            break
        
        dq.popleft()
        idx -= 1
        count += 1
        
    print(count)
    test_cases -= 1

풀이

첫번째 while문은 복수의 test cases를 고려하기 위함이다. 두번째 while문이 풀이의 핵심인데 살펴보면 다음과 같다.

중요도(impts)가 queue에 들어가 있다.
queue의 가장 앞쪽(가장 왼쪽)의 중요도 값이 queue에 들어있는 전체 중요도 값들 중 최댓값이 아니라면 queue의 가장 앞의 값을 가장 뒤로 보낸다. 나머지 값들은 하나씩 앞으로 당겨진다.
이것을 deque의 rotate()를 사용해 구현한다.
처음에 언제 출력되는지 알고 싶은 문서의 위치를 idx로 받았으므로 idx도 매번 변경해준다.

만약 현재 queue의 가장 앞의 값이 queue 전체의 최댓값이라면 while문이 종료된다. 이때 만약 idx가 0이라면, 즉 현재 가장 앞의 값이 최댓값이면서 출력 순서를 알고자 하는 문서라면 count를 증가시키고 queue를 순회하는 while문을 종료시킨다.

이때 count는 우리가 추적하는 문서 외에도 증가될 수 있다. queue의 가장 앞의 값이 최댓값이지만 우리가 추적하는 문서가 아닐 때에도 queue에서 pop하고 count를 증가시킨다. 이를 통해 어떤 문서가 출력될 때마다 count를 증가시키고 추적하는 문서가 출력됐을 때의 count값을 얻을 수 있다.

근거

첫번째 while문은 테스트 케이스를 돌리기 위해 작동하므로 두번째 while문부터 보면 다음과 같은 연산 과정을 거친다.

queue 안의 가장 앞 원소에 대해
1) 최댓값을 구해 그것과 비교한다.(max) → O(N)
2) 최댓값보다 작다면 맨 뒤로 이동한다.(rotate) → O(k) (여기서는 rotate(-1)이므로 O(1))
3) 최댓값이면 queue에서 제거하고 count를 1 증가시킨다. → O(1)

최악의 경우를 상상해보자. queue에 포함된 각 문서의 중요도가 오름차순이라면 전체 queue를 한바퀴 돌아야만 가장 앞의 원소가 pop될 수 있다. 그렇게 최댓값이 한번 빠지고 나면 또다시 한바퀴를 돌아야 한다. 이것을 원소가 모두 빠질 때까지 반복한다.
즉 N + (N-1) + ... + 1 = N(N+1)/2 이다. → O(N^2)

즉 시간복잡도는 O(N^3)이 된다.

이때 N은 100보다 작거나 같은 자연수이므로 최악의 경우에도 1,000,000의 연산횟수를 갖는다. 이는 시간제한에 걸리지 않는다.