[코드트리 조별과제] 정렬을 다루는 자료구조 in Java

PQ를 써야하는 순간은 보통 자신이 정한 정렬기준을 통해 지속적으로 정렬상태를 특정 시점마다 유지하고 싶을때 사용한다.

 

생각해보면 PQ만 정렬을 보장해주는 자료구조가 있는것은 아니다.

 

Java에는 PQ, TreeMap, TreeSet 이 있다.

 

각각 어떨때 쓰는것이 좋을까?

 

TreeSet의 경우에는 PQ와 거의 동일하다.

 

오히려 TreeSet은 최대(first) 최소(last)를 관리하기 더 편하며, 특정 값 바로 이상(floor), 초과(higher), 이하(ceiling) 그리고 미만(lower)인 값을 꺼내는데 유용하다.

 

하지만 TreeSet은 어디까지나 Set을 기반으로 한 OrderedSet이라는것을 잊으면 안된다.

 

즉, 정렬의 대상이되는 원소에 대한 중복을 허용치 않는다는점이다.

 

예를들어서 어떤 문제가 최대 최소, 혹은 중앙값을 관리해야하는 문제인데, 중복원소가 등장하지 않는다는 조건이면 TreeSet을 두개 사용하여 풀겠지만, 중복원소가 등장한다면 TreeSet은 배제할 것이다.

 

TreeMap은 만약 TreeSet의 중복원소를 허용한다는 단점을 어느정도 카운팅을 통해 해결할 수 있다.

 

TreeMap이나 TreeSet을 사용할 때 주의할 점은, 정렬기준을 잘 잡아야 한다는 것이다.

 

해당 정렬기준 원소가 모든 원소에 대하여, 중복되는 랭크가 없이 정렬이 깔끔하게 되어야 한다는 의미이다.

 

(무조건적으로 구분되는 index 값과 같은 기준이 해당 예시가 된다.)

 

이것이 일반적으로는 큰 문제가 되지않지만,

 

원소를 제거하는 연산이거나 뽑는 메소드 (pollXXX, pollXXXEntry 그리고  remove )의 경우

 

의도치않은 원소를 삭제할 수 있기 때문에 주의 해야한다.

 

아래는 PQ를 사용하여 해결 한 문제로 [ 정원 입장은 선착순 ] 이라는 문제이다.

 

결국 도착시간에 따라 정렬하되, 한사람씩 입장이 된다는점이 중요하다.

 

한사람씩 입장하면 그 사람이 점유하고있는 동안 다른사람들이 도착할 수 있다. 이 도착하는데 있어서 유실되는 사람이 없도록 대기자 명단을 관리하는 자료구조가 필요한데

 

이 때 사용되는것이 PQ이다.

 

그냥 Queue를 써도되지않냐? 라고 생각들 수 있지만,

 

정렬기준을 새롭게 잡아야 하기 때문에(번호표 기준) 그래서 PQ를 사용하는 것이다.

 

주의할 점으로는, 대기자 명단을 처리하는 동안에도 언제든 도착시간에 의해 겹치는사람이 있을 수 있다는점을 간과하면 안된다.

 

아래는 문제를 해결한 코드이다.

import java.util.*;
import java.io.*;


public class Main {
    static StringTokenizer stk;
    static int n;
    static int[][] info;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        info = new int[n][3]; // n: 10만
        for(int i = 0;i<n;i++){
            stk = new StringTokenizer(bf.readLine());
            info[i][0] = Integer.parseInt(stk.nextToken()); // a:도착시각 ~ 10억
            info[i][1] = Integer.parseInt(stk.nextToken()); // t:이용시간 ~ 10000
            info[i][2] = i; // 번호표 1 ~ N
        }
        // 이들 중 가장 오래 기다려야 하는 사람이 기다리는 시간을 출력
        // 정원에는 한사람만 들어갈 수 있고, 기다리는사람이 여럿이라면 숫자가 작은 사람부터 들어갈 수 있음
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->{
            return a[2] - b[2];
        }); // 번호표에 따라 오름차순

        Arrays.sort(info, (a, b)-> { 
            if(a[0] == b[0]){
                return a[2] - b[2];
            }
            return a[0] - b[0];
        });
        // 먼저 도착한 순서로 오름차순
        // 도착순서가 같다면, 번호순으로 오름차순
        int ans = 0;
        int pTime = info[0][0] + info[0][1]; // 일단 한사람 우선 넣기
        int ptr = 1;
        while(ptr < n){
            while(ptr < n && info[ptr][0] < pTime){
            	// 현재까지 계산된 마지막 사람이 이용한 뒤의 시각보다 먼저 도착하는사람 대기열에 넣기
                pq.add(new int[]{ info[ptr][0], info[ptr][1], info[ptr][2] });
                ptr++;
            }
            // 만약 위의 while문이 break가 걸렸다는건 지금 ptr이 가리키는 사람은 기다리지 않고 들어가도 되는 사람임
            if(!pq.isEmpty()){
            	// 그러면 지금까지 대기열에 걸린 사람들을 하나씩 처리
                // 여기서 while(!pq.isEmpty())를 하지않는 이유 생각해보기
                int[] now = pq.poll();
                int cha = pTime - now[0];
                ans = Math.max(ans, cha);
                pTime += now[1];
                continue;
            }
            if(ptr < n && info[ptr][0] >= pTime){
            	// 만약 현재 가리키는 사람이 대기열과 관계없이 입장 가능하다면 처리하기
                pTime = info[ptr][0];
                pTime += info[ptr][1];
                ptr++;
            }
            
        }
        System.out.println(ans);
    }
}