[LeetCode#406] Queue reconstruction by height

 

❒ 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]);
}

 

 

 

 

 

 

---