백준1966 프린터 큐

작성일 | In

문제 링크

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

문제 출처

  • 2006 ACM-ICPC NWERC F번

사용 알고리즘

  • 큐
  • 우선순위 큐

시간복잡도

  • O(n^2 log n)

풀이

간단하게 풀이 과정을 써보자면,

  1. 정답을 저장할 변수 ans를 선언하고 0으로 초기화
  2. n개만큼 중요도를 입력받고, 큐에 {중요도, 인덱스} 와 같은 형태로 저장
  3. 큐에서 데이터를 하나 꺼내서 중요도는 order, 인덱스는 idx로 나타냅니다.
  4. 큐에 있는 모든 데이터의 가중치 중 가장 큰 값을 max라 합니다.
  5. order와 max가 같으면 문서가 인쇄되는 것 이므로 ans를 증가 시킵니다.
  6. order와 max가 같으면서 m과 idx가 같으면 꺼낸 값의 중요도가 최대이면서 문제에서 관심있어하는 문서가 현재 문서라면 ans를 출력합니다.
  7. 만약 4번 과정에서 order와 max가 다르면 문서가 인쇄되지 않으므로 다시 큐에 push합니다.
  8. 2번 부터 6번 까지의 과정을 큐가 비워질 때 까지 반복합니다.

1번 과정에서는 데이터를 pair로 저장해 큐에 집어넣습니다.
3번에서 가장 큰 값을 고를 때에는 priority_queue(우선순위 큐)라는 자료 구조를 사용합니다.
우선순위 큐는 pop을 할 때 가장 큰 값을 뱉어냅니다. 그 값에는 .top() 으로 접근합니다.
이 성질을 이용해 최대 값을 쉽게 구할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

void testcase(){
    int n, m;
    int ans = 0;
    queue<p> q;
    priority_queue<int> pq;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        int tmp; scanf("%d", &tmp);
        q.push(make_pair(tmp, i)); //{중요도, 인덱스} 형태로 저장
        pq.push(tmp);
    }
    while(!q.empty()){ //큐가 빌 때 까지
        p poped = q.front();
        q.pop();
        if(pq.top() == poped.first){ //최대값과 현재 문서의 중요도가 같은지 비교
            ans++; //하나를 출력하니까 ans 1 증가
            pq.pop(); //우선순위 큐에서 최대값 pop
            if(poped.second == m) break; //현재 문서의 중요도가 최대이고, 그 문서가 내가 찾고자 하는 문서이면 반복문 종료
        }else q.push(poped);
    }
    printf("%d\n", ans);
}

int main(){
    int t; scanf("%d", &t);
    while(t--){
        testcase();
    }
}