[baekjoon] 1966. 프린터 큐

✅ 문제

 

---

 

 

 

문제 해석부터 해보자

1. 일반 프린터와 달리 중요도가 높은 순으로 문서 출력
2. 중요도가 높은 문서를 제일 앞에 배치
3. 앞에 있던 문서들은 순서대로 뒤에 배치
4. 주어진 인덱스에 위치한 문서의 출력 순서를 리턴함

 

그림을 그려서 이해해 보자면, 아래와 같다.

입출력 예시를 보면 첫 줄은 테스트 케이스 수로 3이다.

아래에는 두 줄씩 조건이 각 테스트케이스마다의 조건이 주어져있다.

 

예를 들어, 두번째 케이스는 아래와 같이 설명할 수 있다. 

 

 

---

 

✅ 풀이

from collections import deque

# 사용자에게 숫자 하나 입력 받아서 그 횟수만큼 테스트케이스 돌림(3)
T = int(input())

for i in range(T):
    # 사용자가 입력한 수를 공백으로 나누어 N, M값 지정(4 2)
    N, M = map(int, input().split())
    
    # 중요도: 사용자 입력값을 공백으로 분리해 deque를 생성하고 담음(1 2 3 4)
    imp = deque(map(int, input().split()))
    
    # 인덱스 번호(0~3)
    index= deque(list(range(N))) 

	# 몇 번째 출력인지 확인하는 변수
    count = 0 

	# 남은 문서가 있을 동안
    while imp:
        if imp[0]==max(imp): #첫 번째 문서의 중요도 = 가장 높은 중요도
            imp.popleft() # 첫 번째 문서 출력하여 제거
            count+=1 # 출력 횟수 올림
            
            if idx.popleft() == M: # 첫 번째 인덱스가 확인하려는 인덱스와 일치하면
                print(count) # 몇번째인지 횟수 출력
                
        else: # 출력 순서가 안됐을 경우 삭제 후 가장 오른쪽에 추가
            imp.append(imp.popleft())
            idx.append(idx.popleft())

 

 

데크를 이용하여 왼쪽 끝 요소 삭제 popleft(), 오른쪽 끝 추가 append로 해결하였다.

 

💡 Point
1. 문서 중요도, 인덱스 번호 묶어서 함께 움직이기
2. 첫 번째 요소가 중요도 max 값일 때만 출력
   2-1) 요소 제거
   2-2) 출력 횟수 올리기
3. max값이 아닐 때는 요소 제거 후 오른쪽 끝에 추가