문제 개요
줄을 서 있는 사람들의 목록이 무작위 순서로 주어졌다고 가정해 보겠습니다. 각 사람은 두 개의 정수 쌍 (h, k)으로 표현됩니다. 여기서 h는 그 사람의 키이고, k는 이 사람 앞에 서 있는 사람 중 키가 h 이상인 사람의 수를 의미합니다.
우리는 이 정보만 가지고 원래 대기열을 재구성하는 알고리즘을 작성해야 합니다.
참고 − 사람 수는 1,100명 미만이라고 가정합니다.
예시 − 입력 대기열이 다음과 같다면,
const arr = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]];
출력 대기열은 다음과 같아야 합니다.
const output = [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]];
접근 방식: 그리디 알고리즘
이 문제는 그리디(Greedy) 방식으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음 두 단계로 요약됩니다.
- 사람들을 키 내림차순으로 정렬합니다. 키가 같은 경우에는 k 값이 작은 순서대로 정렬합니다.
- 정렬된 순서대로 각 사람을 결과 배열의 k번째 위치에 삽입합니다.
키가 큰 사람부터 먼저 배치하면, 이후에 삽입되는 사람(키가 작거나 같은 사람)은 이미 배치된 사람들 사이에 들어가더라도 그들의 k 조건을 깨뜨리지 않습니다. 따라서 삽입 시점의 k 값이 곧 정확한 삽입 위치가 됩니다.
구현 예제
이를 JavaScript 코드로 구현하면 다음과 같습니다.
const arr = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]];
const reconstructQueue = data => {
const result = [];
// 키는 내림차순, 키가 같으면 k는 오름차순으로 정렬
const sorter = (a, b) => {
return b[0] - a[0] || a[1] - b[1];
};
data.sort(sorter);
// 각 사람을 k번째 인덱스에 삽입
for (let i = 0; i < data.length; i++) {
result.splice(data[i][1], 0, data[i]);
}
return result;
};
console.log(reconstructQueue(arr));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]
동작 과정 살펴보기
정렬이 끝나면 배열은 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]가 됩니다. 이 순서대로 각 사람을 k번째 위치에 삽입하면 다음과 같이 진행됩니다.
- [7,0] → 인덱스 0에 삽입 → [[7,0]]
- [7,1] → 인덱스 1에 삽입 → [[7,0], [7,1]]
- [6,1] → 인덱스 1에 삽입 → [[7,0], [6,1], [7,1]]
- [5,0] → 인덱스 0에 삽입 → [[5,0], [7,0], [6,1], [7,1]]
- [5,2] → 인덱스 2에 삽입 → [[5,0], [7,0], [5,2], [6,1], [7,1]]
- [4,4] → 인덱스 4에 삽입 → [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
최종적으로 올바른 대기열이 완성됩니다. 시간 복잡도는 정렬에 O(n log n), 삽입 과정에 O(n²)이 소요되므로 전체적으로 O(n²)입니다. 다만 사람 수가 1,100명 미만으로 제한되어 있으므로 충분히 효율적인 접근 방식입니다.