[ 백준 1966 ] 프린터 큐

1. 문제 링크 https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

2. 문제 

3. 문제 요약

 N개의 문서가 우선순위 큐에 있을 때, M번째 문서의 출력순서를 찾는 문제이다.

 

4. 문제 풀이

(1) Heap ? Array

  일단 우선순위 큐라는 점에서 Heap를 사용할 지, 일반 array를 사용할지 고민을 했다.

 

Heap 을 이용한다면,

데이터들을 입력받는 대로 Heap 구조에 삽입하고, 입력이 끝나면 정렬시킨 후 탐색하는 방법을 생각했고,

 

Array반복탐색을 이용한다면,

데이터를 입력받는 대로, Max 우선순위부터 min 우선순위까지 반복적으로 탐색하는 방법을 생각했다.

 

 Heap을 만들어 정렬한 뒤, M의 순서를 찾는 방법은 O(N*logN) 의 복잡도를 갖고

 Array를 만들어 정렬한 뒤, M의 순서를 찾는 방법은 O(N * p) 의 복잡도를 갖는다. (p = 우선순위 범위) 

N <= 100, p = 9 이므로, Heap이 빠르겠다는 생각은 했지만, 

구현하기도 쉬우면서 성능에 큰 차이가 없기 때문에 Array 반복 탐색을 하기로 했다.

 

 (2) Array 탐색

 우선 두개의 Array를 바탕ㅇ로 진행한다.

 int arr[] = int[ N ]:  각 문서들의 우선순위가 담겨있는 배열

 int priority[] = int[ #중요도 ] : 해당 우선순위의 갯수

   배열내의 가장 높은 우선순위부터 시작해서,

 해당 값을 지니는 값들을 발견하면

 1. arr의 값을 0으로 만들고,

 2. priority[해당 우선도]의 숫자를 감소하고,

 3. 출력된 갯수를 증가시킨다.

반복탐색하면서 arr[M] = 0이 되면 종료.

 

5. 풀이 코드

 

public static void problem1966() throws Exception {
    stk = new StringTokenizer(br.readLine());
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    page= new int[N];
    priority = new int[10];
    stk = new StringTokenizer(br.readLine());            
    for (int i = 0; i < N; i++) {
        page[i] = Integer.parseInt(stk.nextToken());
        priority[page[i]]++;
    }
    bw.write( printing()+ "\n");
}