PriorityQueue forEach() 는 정렬되어 조회되지 않는다?!

오늘의 주제는

PriorityQueue의 forEach 메서드의 조회 순서

입니다.

 

여느때와 같이 알고리즘 문제를 풀고 있었는데.. 

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

- 문제 보고 오세용

 

자꾸 내 코드가 맞는데 틀렸다고~ 틀렸다고~ 하는거 아닙니까.

진심으로다가 집 가야되는데 계속 틀렸다니까 집도 못 가고! 밥도 못 먹고! ㅠㅠ

 

아무튼 제가 작성했던 답은 아래와 같습니다.

여러분들을 위해 주석을 꼼꼼히 달아봤어용.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // 종료 시간 기준 후보
    static PriorityQueue<int[]> timeCandis = new PriorityQueue<>((c1, c2) -> c1[0] - c2[0]);  // 종료 시간, 좌석 번호
    // 테이블 번호 기준 후보
    static PriorityQueue<int[]> tableCandis = new PriorityQueue<>((c1, c2) -> c1[1] - c2[1]);  // 종료 시간, 좌석 번호

    public static void main(String[] args) throws IOException {
    	// 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        List<int[]> times = new ArrayList<>();  // 시작 시간, 종료 시간
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            times.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }
        
        // 싸지방 사용 시간 정렬 (시작 시간 기준)
        times.sort(Comparator.comparingInt(t -> t[0]));

        int idx = 0;
        int[] tables = new int[N];  // 자리 사용 횟수 저장 배열
        tables[idx]++;
        timeCandis.add(new int[]{times.get(0)[1], idx++});

        for (int i = 1; i < N; i++) {
            int[] now = times.get(i);
            // 시간 변경 + 사람 더 앉음 -> time & table candidates 다시 검사해줌
            checkEndTime(now[0]);

            // idx 전에 빈 자리가 있으면 해당 자리에 앉힘
            // 사람이 앉으면 timeCandis에 무조건 넣음
            if (!tableCandis.isEmpty()) {
                int[] candi = tableCandis.poll();
                timeCandis.add(new int[]{now[1], candi[1]});
                tables[candi[1]]++;
            } else {  // idx 전에 빈 자리 없으면 idx에 앉히고 하나 늘림
                tables[idx]++;
                timeCandis.add(new int[]{now[1], idx});
                idx++;
            }
        }
		
        // 출력
        sb.append(idx).append("\n");
        for (int i = 0; i < idx; i++) {
            sb.append(tables[i]).append(" ");
        }
        System.out.println(sb);
    }

    static void checkEndTime(int now) {
        int cnt = 0;
        // 우선순위 큐인 timeCandis에서 하나씩 조회 -> 종료 시간이 현재 시간보다 적은 것.
        // 즉, 이미 사용 종료된 자리 정보는 사용 가능한 자리이기 때문에 tableCandis에 넣음
        // tableCandis에 넣은 만큼 timeCandis에서 빼기위해 cnt 세줌.
        for (int[] time : timeCandis) {
            if (time[0] < now) {
                tableCandis.add(time);
                cnt++;
            } else {
                break;
            }
        }
        // cnt 만큼 timeCandis에서 빼줌
        for (int i = 0; i < cnt; i++) {
            timeCandis.poll();
        }
    }
}

중요한 부분은 checkEndTime 메서드입니다.

저는 우선순위 큐를 forEach로 조회하면 우선순위대로 (순서대로) 조회될 거라고 생각했습니다.

하지만 PriorityQueue를 forEach는 순서대로 조회되지 않습니다..

 

 

이제 그 이유를 알아보겠습니당.

 

PriorityQueue의 forEach메서드를 보겠습니다.

es라는 배열을 순서대로 조회하는데 es는 queue네요.

그럼 이제 queue를 보겟슴다.

 

저같은 사람을 위해 상세하게 주석 설명이 있네요.. 고마워라

가장 작은 값(우선순위 0번째)의 인덱스가 0인 것은 맞습니다.

하지만 제가 간과한 부분! 우선순위 큐는 힙이기 때문에 완전 이진 트리 구조입니다.

오름 차순을 정렬 기준으로 했을 때, 부모 노드는 자식 노드보다 클 수 없죠.

이것은 트리를 순서대로 방문하면 되는 완전히 정렬된 상태는 아니라는 것을 뜻합니다. (첫 노드는 최솟값이라는 것은 보장 가능. 무조건 보장!)

 

또한, 위의 설명에 있듯이 queue 배열은 그저 트리를 배열에 담은 것 뿐입니다. 순서대로 말이죠.

그러니까 queue[n]의 자식이 queue[2 * n + 1]과 queue[2 * (n + 1)] 인 것이죠.

 

저는 우선순위 큐 자료구조의 특성은 제끼고 그냥 아~ 우선순위니까 차례대로 조회하게 해주겠지~ .... 라고 생각하고 위와 같은 코드를 짜게 됐던 것입니다. 허허 뭐든 잘 알고 사용하는게 정말정말.. 중요하죠

 

---

 

그럼 제가 짠 코드를 고쳐봐야겠죠잉?

 

public class Main {
    // 종료 시간 기준 후보
    static PriorityQueue<int[]> timeCandis = new PriorityQueue<>((c1, c2) -> c1[0] - c2[0]);  // 종료 시간, 좌석 번호
    // 테이블 번호 기준 후보
    static PriorityQueue<int[]> tableCandis = new PriorityQueue<>((c1, c2) -> c1[1] - c2[1]);  // 종료 시간, 좌석 번호

    public static void main(String[] args) throws IOException {
        ```
    }

    static void checkEndTime(int now) {
        while (!timeCandis.isEmpty()) {
            int[] time = timeCandis.peek(); // [1]
            if (time[0] < now) {
                tableCandis.add(time);
                timeCandis.poll();  // [2]
            } else {
                break;  // [3]
            }
        }
    }
}

 

[1] peek()로 timeCandis의 첫 노드. 즉, 종료 시간이 가장 빠른 노드를 가져옵니다. 이 종료 시간이 현재 시간 이전이면 해당 자리는 빈 자리인 것이죠

[2] 그럼 해당 노드는 빼줘야 합니다. 왜냐? tableCandis에 넣어줘야 하거든요. 여기는 비어있는 자리를 저장하는 우선순위 큐 공간이랍니다.

[3] 만약 timeCandis에서 peek()로 조회한 종료 시간이 가장 빠른 노드가 현재 시간보다 이후 시간이면 더이상 해당 큐에는 현재 시간보다 빠른 노드는 존재하지 않는 거겠죠잉? 그럼 그~냥 바로 해당 반복문을 탈출!하는겁니다.

 

 

이렇게 해서 백준 싸지방에 간 준하 문제는 해결되었습니다. 짜란~

정말.. 다양한.. 시도들을 해봤어요.. 이건가? 하면서 고치다가 시간초과까지 나버림. 하핫

 

정말 왜 통과 못하는지 도무지 모르겠었는데 해결해서 기분이 좋네용. 햅삐~