Queue Reconstruction by Height

사람의 정보를 담은 배열 people이 주어진다. 각 정보 people[i]는 (h, k) 쌍인데 h는 이 사람의 키이고 k는 이 사람 앞에 이 사람의 키 h보다 크거나 같은 사람이 정확히 k명 있어야 한다는 조건을 뜻한다.

이 큐를 재구성해서 이 조건에 맞게 사람들 줄을 다시 세우자.

배열의 크기는 1 ~ 2,000 이고 키는 \(0 \sim 10^6\), k는 0 ~ people.length 이다. 큐는 항상 재구성할 수 있음이 보장된다.

예를 들어 [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]를 생각해보자. 정답은 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]이 되는데, 그 이유는:

[5,0]은 키가 5이고 앞에 자기보다 키가 크거나 같은 사람이 0명이다.
[7,0]은 키가 7이고 앞에 자기보다 키가 크거나 같은 사람이 0명이다.
[5,2]는 키가 5이고 앞에 자기보다 키가 크거나 같은 사람이 2명이다.
[6,1]은 키가 6이고 앞에 자기보다 키가 크거나 같은 사람이 1명이다.
[4,4]는 키가 4고 앞에 자기보다 키가 크거나 같은 사람이 위의 네 명 모두이다.
[7,1]은 키가 7이고 앞에 자기랑 키가 크거나 같은 사람이 1명 뿐이다.

탐욕

일단 키가 큰 친구를 먼저 배치하는 게 유리해보인다. 배열을 키의 내림차순으로 정렬했다고 해보자. 그러면 키 큰 순서대로 바로 배치하면 끝이다.

키가 같은 경우에는 k가 더 작은 친구를 앞에 배치하는 것이 항상 유리하다. 따라서, 같은 키에 한해서는 k의 오름차순으로 정렬을 해야 한다. 이 경우, k가 작은 순서대로 배치하면 된다.

그럼 배치는 어떻게 해야할까? 이 경우 스택처럼 뒤에 붙이는게 아니라, 줄을 세워야 하므로 중간에 껴 넣어야 한다. 만약 위의 조건대로, 즉 (키가 큰 순서, 키가 같으면 k가 작은 순서)로 친구를 배치한다면, 친구를 곧바로 k 위치에다가 배치하고 나머지 친구를 뒤로 싹 밀면 된다. 예를 들어 [[7,1], [6,1], [7,0]]이 있을 때:

(키 내림차순, k 오름차순)으로 정렬하면 [[7,0], [7,1], [6,1]]이 된다.
앞의 두 명을 배치하는 일은 자명하게 [[7,0], [7,1]]이 된다. 이제 [6,1]을 배치해야 하는 경우를 잘 생각해보자. 이미 자기보다 키 큰 친구들을 모두 배치했으므로, [6,1]은 곧바로 k 위치에 배치하면 조건을 만족하게 된다. 즉, 자기보다 크거나 같은 친구가 정확히 k명 있게 된다.

정리하면,

키 기준으로 내림차순, k 기준으로 오름차순으로 정렬한다.
순서대로 배치하는데, 이때 k 위치에다 친구를 배치하고 나머지 친구를 전부 뒤로 밀어버린다. 그러면 항상 조건을 만족하게 된다.

이 놀라운 아이디어를 구현하면 다음과 같은 매우 심플한 코드가 완성된다.

def reconstructQueue(people):
    queue = []
    for p in sorted(people, key=lambda x: (-x[0], x[1])):
        queue.insert(p[1], p)
    return queue

정렬 조건으로 키 내림차순과 k 오름차순을 동시에 만족해야 하므로 key 함수에 튜플을 넘겨줬다.
파이썬에서 array.insert(index, value) 함수는 index 위치에 value를 집어넣고 원래 값들을 싹 뒤로 밀어버린다. 정확히 우리가 원하는 함수이다. p[1]이 k이고 이걸 곧바로 인덱스로 쓰면 되기 때문에 저런 코드가 나온다. 범위가 배열보다 크면 그냥 제일 마지막에 추가된다.

이렇게하면 insert의 복잡도 때문에 전체 복잡도는 \(O(N^2)\)이 된다.