[C++] 백준 1966번 프린터 큐

자료구조 큐를 사용해서 푸는 문제.

큐의 선입선출 구조를 이용해서 문제를 풀면된다.

 

문제 풀이

문제를 다 읽으면 어떤 방식으로 구현해야 하는지는 이해하기 쉽다.

테스트 케이스 중 6 0 / 1 1 9 1 1 1을 입력하게 되면 pop되는 순서를 알아보자면

1. 최대값 9, 맨 앞 1 맨 뒤로 간다.
2. 최대값 9, 맨 앞 1(원래 첫번째) 맨 뒤로 간다.
3. 최대값 9, 맨 앞 9(원래 두번째) pop된다.
4. 최대값 1, 맨 앞 1(원래 세번째) pop된다.
5. 최대값 1, 맨 앞 1(원래 네번째) pop된다.
6. 최대값 1, 맨 앞 1(원래 다섯번째) pop된다.
7. 최대값 1, 맨 앞 1(원래 0번째) pop된다.
8. 최대값 1, 맨 앞 1(원래 첫번째) pop된다.

따라서 우리가 구하고 싶은 0번째 수는 5번째에 pop되는 것을 알 수 있다.

 

이해는 하기 쉽지만, 이를 어떻게 구현할 수 있을까?

우리는 각 case마다 최대값이 무엇인지, 또한 최대값을 몇 개 가지고 있는지 알아야 한다.

사용한 STL과 변수

queue STL을 사용해서 priority_queue를 사용하고, queue를 사용할 것이다.

테스트 케이스 t, 프린터 큐에서 원소의 개수 n, 그리고 내가 찾고 싶은 수가 몇번째인지 저장하는 want_idx를 변수로 설정했다.

메인함수 - 1

우선 priority_queue pq는 우선순위 큐로, less 순서로 정렬시켰으므로 내림차순으로 정렬이 된다.

이는, 최대값이 무엇이고 몇 개 있는지 저장하기 위해 선언한 변수이다.

그리고 queue q는 처음에 입력받을 때 넣어주는 우리가 살펴보아야 할 큐이다.

문제에서 프린트라고 생각하면 된다.

또한 큐에서 pair 자료형을 사용하는데 first는 중요도 second는 index를 저장한다.

메인함수 - 2

for 반복문을 돌면서, q의 맨 앞 부분과 pq의 맨 앞 부분이 일치하는지 살펴본다.

pq의 맨 앞부분은 항상 큐의 최대값을 나타내고 있으므로 최대값만 살펴보게 된다.

만일 같지 않다면 같아질 때 까지 q의 맨 앞 원소를 pop()했다가 다시 push()해준다.

 

같아졌을 때, 두 큐에서 모두 pop해주고, 만일 현재 큐에서 꺼낸 원소가 내가 원래 찾던 원소의

맨 처음 index였다면 반복문을 종료시키고 결과값을 출력한다.

 

실버3 자료구조 큐 문제

생각하느라 시간이 좀 걸렸지만 쉽게 풀 수 있었다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.