[백준/Python] 1966 프린터 큐

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

 

 

사용 알고리즘: 큐

 

 

입력

• 첫 줄에 테스트케이스 수
• 각 테스트케이스별로
• 첫 줄에는 N (1 <= N <= 100), 몇 번째로 인쇄되었는지 궁금한 문서가 현재 큐의 몇 번째에 놓여 있는지 나타내는 정수 M (0 <= M < N)
• 두번째 줄에는 N 개의 문서의 중요도가 차례로 주어짐 (1 이상 9 이하의 정수, 같은 중요도가 있을 수 있음)

 

규칙

1. 현재 큐의 맨 앞에 있는 문서의 중요도를 확인

2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 큐의 가장 뒤에 배치하고 그렇지 않다면 바로 인쇄

 

 

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

T = int(input()) # 테스트케이스 수

for _ in range(T):
    N, M = map(int, input().split()) # N, M 
    input_values = list(map(int, input().split())) # 각 문서의 중요도
    # 문서의 인덱스와 중요도를 묶어서 큐에 넣음 -> [[인덱스, 중요도], [인덱스, 중요도] , ..]
    importance = deque([index, value] for index, value in enumerate(input_values))
    find_value = importance[M] # 궁금한 문서를 저장해 놓음
    count = 0 # 인쇄될 때마다 갱신해주는 count 값
    stop = 1 # while 문을 돌지 안돌지 결정해주는 값

    while stop:
        MAX = max(importance, key=lambda x: x[1]) # 현재 문서들의 중요도 최대값
        if MAX[1] > importance[0][1]: # 최대값이 더 크다면 맨 앞에 있는 요소를 떼서 맨 뒤에 붙임
            importance.append(importance.popleft())
        else: # 그렇지 않다면 맨 앞 요소를 제거
            num = importance.popleft()
            count += 1 # count 증가시킴
            if num == find_value: # 궁금한 문서와 현재 제거(프린트)된 문서가 같다면 count 출력
                print(count)
                stop = 0 # 궁금한 문서의 프린트 순서를 알았으니 while 문 탈출

 

출력 순서가 궁금한 문서의 중요도와 인덱스를 알고 있어야 하기 때문에 importance(큐) 에 [인덱스, 중요도] 로 묶어서 집어넣었다. 

인덱스 값이 필요한 이유는 중요도가 같은 문서가 여러개 있을 경우 중요도만 가지고 정확한 출력 순서를 구하기 힘들기 때문이다. 

 

현재 큐에 있는 문서 중 중요도가 제일 높은 문서를 찾아서 MAX 에 저장해두고, 아래와 같이 처리를 했다.

• 큐의 맨 앞 문서의 중요도가 MAX 보다 작음 -> 떼서 큐의 맨 뒤로 이동시킴
• 큐의 맨 앞 문서의 중요도가 MAX 보자 작거나 같음 -> 제거 (프린트 시킴)

큐의 맨 앞 문서의 중요도가 MAX 보다 작거나 같은 경우에는 프린트가 되는 경우이므로 count 를 증가시켜주었다. 

그리고 프린트 되는 문서가 출력 순서가 궁금한 문서와 동일한 문서라면 count 를 출력하고 stop 을 0 으로 바꾸어 while 문 도는 것을 중단시켰다. 

 

 

풀고나서 더 간단하게 풀 수 있는 방법이 있을까 궁금해서 다른 사람들 코드를 찾아보았는데, 더 간단하게 푼 코드가 있어서 가져와보았다. 

from collections import deque
import sys

t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    queue = deque(list(map(int, sys.stdin.readline().split())))
    count = 0
    while queue:
        best = max(queue)  #현재의 최댓값이 가장 먼저 배출되므로 최댓값을 저장
        front = queue.popleft() # 큐의 front를 뽑았으므로
        m -= 1 # 내 위치가 한 칸 당겨진다.

        if best == front: # 뽑은 숫자가 제일 큰 숫자일 때
            count += 1 # 하나가 영원히 배출되므로 순번 하나 추가
            if m < 0: # m이 0이라는 것은 뽑은 숫자가 내 숫자라는 뜻.
                print(count)
                break

        else:   # 뽑은 숫자가 제일 큰 숫자가 아니면
            queue.append(front) # 제일 뒤로 밀려나게 됨
            if m < 0 :  # 제일 앞에서 뽑히면
                m = len(queue) - 1 # 제일 뒤로 이동

 

나처럼 인덱스와 중요도를 묶어서 저장하지 않고, 궁금한 문서의 인덱스를 문서의 이동에 따라 갱신시켜주는 방식이었다. 

내가 짠 코드와 기본적인 알고리즘이 동일하기 때문에 O(T * n^2) 으로 시간 복잡도가 같고, 백준에서 코드를 돌렸을 때 성능이 비슷했지만, 훨씬 쉽게 읽히는 코드인 것 같다. 

 

그리고 이 문제에서 문서의 개수는 최대 100 개로 제한되어 있지만, 문서의 개수가 훨씬 많아지면 내 코드보다 메모리를 덜 쓰게 되기 때문에 성능 차이가 생기지 않을까 싶다. 코드를 더 간결하게 짤 수 있는 방법을 많이 생각해봐야겠다. 

 

코드를 가져온 블로그

https://hongcoding.tistory.com/42

[백준] 1966번 프린터 큐 (Python 파이썬)

 

 

 

시간 복잡도

 

from collections import deque
import sys
input = sys.stdin.readline

T = int(input()) # O(1)

for _ in range(T): # O(T * n^2)
    N, M = map(int, input().split()) # O(1)
    input_values = list(map(int, input().split())) # O(n)
    importance = deque([index, value] for index, value in enumerate(input_values)) # O(n)
    find_value = importance[M] 
    count = 0
    stop = 1

    while stop: # 최악의 경우 O(n^2)
        MAX = max(importance, key=lambda x: x[1]) # 최악의 경우 O(n)
        if MAX[1] > importance[0][1]:
            importance.append(importance.popleft())
        else:
            num = importance.popleft()
            count += 1
            if num == find_value:
                print(count)
                stop = 0

 

 

while 루프의 시간 복잡도는 O(n^2) 이다. 

 

일단 max 함수는 각 루프마다 최대 O(n) 시간이 걸린다. 

-> 처음부터 끝까지 돌며 최대값을 찾는데, 최대값이 가장 뒤에 있는 경우 O(n) 시간이 걸린다

 

while 루프는 최대 N 번 반복이 된다. 

-> MAX 값이 항상 마지막에 위치하고, 나머지 모든 요소가 한 번씩 큐의 끝으로 이동할 때까지 대기해야 하는 경우 가장 오랜 시간이 걸리게 된다. 각 루프 내의 작업(max 함수 호출)이 O(n) 시간 걸리고, 루프가 최대 N 번 반복될 수 있으니 전체 시간 복잡도는 O(n^2) 시간이 된다. 

 

가장 바깥쪽의 for 문은 T 번 반복되고 안쪽 연산은 아래와 같은 시간이 걸리는데, 가장 큰 시간만 고려하면 되므로 for 문은 O(T * n^2)  시간 복잡도를 갖게 된다. 

• input_values 를 입력받는 과정 importance 에 값을 할당하는 과정 -> 각각 O(n) 
• while 루프 -> O(n^2) 

그래서 총 시간 복잡도는 O(T * n^2) 이 된다.