[LeetCode] 406. Queue Reconstruction by Height

🔈 문제

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [$h_i$, $k_i$] represents the $i^{th}$ person of height $h_i$ with exactly $k_i$ other people in front who have a height greater than or equal to $h_i$.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [$h_j$, $k_j$] is the attributes of the $j^{th}$ person in the queue (queue[0] is the person at the front of the queue). 

 

💫 예시

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

 

🎱 제한

 

• 1 <= people.length <= 2000
• 0 <= $h_i$ <= $10^6$
• 0 <= $k_i$ < people.length

 

🧐 문제 접근 및 풀이

 

사람들을 일렬로 줄을 세웠을 때, 내 키와 내 앞에 있는 사람 중 내 키보다 크거나 같은 사람의 수가 주어진다. 이러한 정보가 주어졌을 때 올바르게 재구성하는 문제이다.

 

가장 먼저 떠오른 방법은 정렬이다. 

 

에를 들어 [[7,2], [7,0], [7,1]] 이 예제로 주어진 경우 [[7,0], [7,1], [7,2]] 로 정렬해야 올바른 답이 된다. $k_i$로 오름차순 정렬된 것을 확인할 수 있다. 그리고 좀 더 뚫어져라 쳐다보면 $k_i$가 현재 자신의 인덱스를 나타내고 있는 걸 발견 가능하다.

 

여기에 [6,3] 이 추가 된 [[7,2], [7,0], [7,1], [6,3]] 을 살펴보자. 이 경우에는 [[7,0], [7,1], [7,2], [6,3]] 이 정답으로 여전히 $k_i$는 인덱스를 나타내고 있다. 

 

그렇다면 [6,3] 이 아닌 [6,1] 을 예시로 들어보자. [[7,2], [7,0], [7,1], [6,1]] 가 주어졌을 때, [[7,0], [6,1], [7,1], [7,2]] 이 정답이 된다. [6,1] 에서 $k$는 현재 인덱스를 나타내고 있지만 [7,1]은 더이상 자신의 인덱스를 나타내고 있지 않는다. 그럼 정렬 알고리즘은 틀린것일까...?

 

그렇지 않다. [7,1]도 [6,1] 이 오기 전까지는 $k$가 자신의 인덱스를 나타내고 있었다. 다시 말해 [6,1] 이 추가되자 이전에 것들의 인덱스는 무시되고, 현재 추가되는 값의 $k$가 더 중요해졌다. 키가 큰 순으로 값을 추가하게 된다면 이후에 추가되는 값들은 어차피 나보다 키가 작을 테니 앞에 오든 뒤에 오든 상관이 없다. 그리고 키가 같은 경우에는 $k$ 오름차순으로 추가하여야 한다.

 

그럼 어디에 추가해야 할까? 바로 $k$, 즉 인덱스에 하면된다.

 

정리하자면, 키 내림차순, 내 키보다 크거나 같은 순은 오름차순으로 정렬하고, 각 원소는 정답 배열 인덱스에 추가하는 방식으로 문제를 해결할 수 있다. 

 

💻 코드

 

Python

 

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        result = []
        for h, k in sorted(people, key=lambda x: (-x[0], x[1])):
            result.insert(k, [h, k])
        return result
 

 

 

Java

 

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a1, a2) -> {
            if (a1[0] != a2[0]) {
                return a2[0] - a1[0];
            }
            return a1[1]-a2[1];
        });
        final List<int[]> res = new LinkedList<>();
        final int n = people.length;
        for (final int[] person : people) {
            res.add(person[1], person);
        }
        return res.toArray(new int[n][2]);
    }
}
 

 

 

Rust

 

impl Solution {
    pub fn reconstruct_queue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        people.sort_by_key(|x| (-x[0], x[1]));
        let mut res = Vec::with_capacity(people.len());
        for person in people.iter() {
            res.insert(person[1] as usize, person.to_vec());
        }
        res
    }
}
 

 

 

시간복잡도는 정렬할 때 $O(n * log n)$, 값 추가할 때 최악의 경우 $O(n)$ 이를 $n$ 번 반복이니까 총 $O(n^2)$ 이 나온다. 

 

자바로 문제 풀 때 ArrayList 말고 LinkedList 사용하면 좀 더 빠르려나? 하고 바꿔보았다. ArrayList 사용하면 값 찾는데 $O(1)$ 그 값 이후에 값들 전부 한칸씩 뒤로 미는 작업이 $O(n)$이고, LinkedList 사용하면 값 찾는데 $O(n)$ 그리고 다음 노드 주소 변경하는데 $O(1)$ 이므로 둘 다 $O(n)$ 이지만, 전부 한칸식 뒤로 미는 작업이 값 찾는 작업보다 오래 걸릴 것 같았다. 하지만 유의미한 차이는 없었다. 

 

그래도 여기서 리스코프 치환원칙의 맛을 봤다. ArryaList로 구현했던 것을 LinkedList로 변경하기 위해서 바꾼 코드는 단 한줄, 객체를 인스턴스화 할 때였다. ps 하면서 객체지향 느껴보는건 거의 처음이었다. 

 

🔗 문제링크