Algorithm/문제풀이

[LeetCode#406] Queue reconstruction by height

gilbert9172 2024. 9. 17. 17:26

 

❒ Description


날짜 2024.09.17 (화)
제목 Queue reconstruction by height
링크 https://leetcode.com/problems/queue-reconstruction-by-height/description/
자료구조 ArrayList, PriorityQueue
알고리즘 그리디
시간 복잡도 O(n)

 

이번 문제는 Priority Queue의 순서 설정, ArrayList의 성질 그리고 index 활용이 필요한 문제이다.

 

 

 

 

 

❒ 문제 분석


우선 먼저 우선순위 큐의 정렬 기준을 세워야 한다.

h가 같은 경우 k 기준으로 오름차순 정렬
h가 같지 않을 경우 h 기준으로 내림차순 정렬

 

그리고 k를 index로 활용하여 person을 정렬한다.

 

 

 

 

 

❒ Solution


public int[][] reconstructQueue(int[][] people) {
    Queue<int[]> pq = new PriorityQueue<>(
        (a,b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]
    );
    
    for (int[] person : people) {
        pq.add(person);
    };
    
    List<int[]> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        int[] person = pq.remove();
        result.add(person[1], person);
    }
    return result.toArray(new int[people.length][2]);
}