[백준] 1966번 - 프린터 큐

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문서의 개수가 100까지밖에 주어지지 않아서

2중 for문을 돌아도 괜찮을 것 같다고 생각을 했다.

 

그러고 나서 현재 Queue가 앞 뒤로 추가/삭제 되면서

해당 문서가 몇 번째 있는 지에 대한 기록을 어떻게 구성해야할지

생각해보던 중 딕셔너리를 이용하지 않고 리스트를 활용해서

스택을 2개 만들어준 뒤, 각각에 동일한 Queue 연산을

수행하여 문제를 풀 수 있겠다는 생각이 들었다.

 

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  q = list(map(int, range(n)))
  rs = list(map(int, input().split()))
  
  if n == 1: print(1)
  else:
    for i in range(n):
      for j in range(n):
        if rs[i] >= max(rs[i:]): break
        else: 
          rs.append(rs[i])
          rs.pop(i)
          q.append(q[i])
          q.pop(i)
    print(q.index(m)+1)

 

인덱싱의 번호를 담당할 q 리스트와

입력에서 받아줄 rs 리스트를 생성한다.

 

n이 1이라면 1개의 문서밖에 존재하지 않기 때문에

1을 출력해주면 되고 그 외의 예외처리를 진행한다.

 

2중 for문을 돌면서 i번째에 있는 수가 i번째를 기준으로 한

리스트 전체의 max 값보다 크거나 같다면 패스하고,

그렇지 않다면 각각의 리스트에 맨 앞 문서를 맨 뒤로 추가하고

맨 앞에 있는 문서를 빼주는 방식으로 Queue를 구현하였다.

 

m은 0번째 문서부터 출발하기 때문에

출력은 인덱스에 1을 더한 값으로 해주면 정답이 된다.

 

실버 3에 해당하는 구현문제여서 만만하게 봤지만,

노트에다가 풀고 코드로 옮기는 과정이 만만하지 않았다..

 

화이팅 💪