관리 메뉴

차근차근

[백준 1966] 프린터 큐 본문

대학교/Algorithm

[백준 1966] 프린터 큐

SWKo 2020. 2. 16. 14:13

0. 제목

  • 백준 1996 프린터 큐
  • BOJ 1996 프린터 큐
  • C++ 1996 프린터 큐

1. 문제

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


2. 풀이

  • 중요도에 따라 출력되는 순서가 다르므로 우선순위 큐를 사용한다.
  • C++ STL의 queue와 priority_queue를 사용한다.
  • 먼저 q의 원소들을 입력받을 때 pair를 이용하여 인덱스와 중요도 값을 쌍으로 입력 받고 q에 push 해준다.
  • 그리고 prioirity_queue<int> pq; 와 같이 우선순위 큐를 선언한다. 우선순위 큐에는 중요도 값만 push 해준다.
  • q의 원소가 0개가 아닌동안 루프를 돈다. q의 가장 먼저 들어온 원소 즉, 가장 앞에 있는 원소의 인덱스와 중요도 값을 변수 nowidx, nowval에 저장한다.
  • 그 후 가장 앞에 있는 원소를 pop을 사용하여 제거한다.
  • 이제 조건문을 수행하는데 현재 중요도 값이 pq 즉, 우선순위 큐의 가장 위에 있는 원소(우선순위 가장 높은 원소)의 값과 같으면 pq.pop()을 수행해준다. 그 후 출력순서를 하나 늘려주고 nowidx가 구하고자 하는 M값과 같다면 출력해주고 반복문을 탈출한다.
  • 만약 우선순위가 pq의 top과 같지 않았다면 q에서 pop을 통해 제거했던 원소를 다시 push 하여 뒤로 넣어준다.
  • 또한, 각각의 test case마다 마지막엔 q가 비어있게 될 것이므로 따로 초기화는 하지 않아도 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <queue>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T;
    
    cin >> T;
    
    for(int i = 0; i < T; i++){
        int N, M, cnt = 0;
        queue<pair<intint>> q;
        priority_queue<int> pq;
        
        cin >> N >> M;
        
        for(int j = 0; j < N; j++){
            int val;
            cin >> val;
            q.push({j, val});
            pq.push(val);
        }
        
        while(!q.empty()){
            int nowidx = q.front().first;
            int nowval = q.front().second;
            q.pop();
            
            if(nowval == pq.top()){
                pq.pop();
                cnt++;
                if(nowidx == M){
                    cout << cnt << '\n';
                    break;
                }
            }
            else{
                q.push({nowidx, nowval});
            }
        }
    }
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 2133] 타일 채우기  (0) 2020.02.17
[백준 4963] 섬의 개수  (0) 2020.02.16
[백준 2170] 선 긋기  (0) 2020.02.15
[백준 1699] 제곱수의 합  (0) 2020.02.15
[백준 1149] RGB거리  (0) 2020.02.13
0 Comments
댓글쓰기 폼