문제 설명
무작위 순서로 줄 서 있는 사람들의 목록이 주어졌다고 가정해 봅시다. 각 사람은 두 정수의 쌍 (h, k)로 표현됩니다. 여기서 h는 그 사람의 키를 의미하고, k는 자신보다 앞에 서 있으면서 키가 h 이상인 사람의 수를 나타냅니다. 우리의 목표는 이 조건들을 모두 만족하도록 대기열을 재구성하는 메서드를 구현하는 것입니다.
예를 들어 입력 배열이 [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]와 같다면, 올바른 출력은 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]이 됩니다.
해결 전략
이 문제는 그리디(Greedy) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '키가 큰 사람부터 먼저 자리를 잡게 한다'는 것입니다. 구체적인 단계는 다음과 같습니다.
- 정렬: 주어진 배열을 다음 비교 규칙에 따라 정렬합니다.
- 두 사람의 키가 같다면(a[0] == b[0]), k 값이 큰 사람이 앞에 오도록 내림차순 정렬합니다.
- 키가 다르다면, 키를 기준으로 오름차순 정렬합니다.
- 결과 벡터 생성: 최종 대기열을 저장할 벡터 ans를 하나 선언합니다.
- 역순 순회 및 삽입: 정렬된 배열의 마지막 요소(키가 가장 큰 사람)부터 첫 번째 요소까지 거꾸로 순회하면서, 각 사람을 ans 벡터의 인덱스 p[i][1] 위치에 삽입합니다.
- 결과 반환: 완성된 ans 벡터를 반환합니다.
왜 이 방법이 동작할까?
키가 큰 사람부터 먼저 배치하면, 이후에 삽입되는 키가 작은 사람들은 이미 배치된 사람들 입장에서 '앞에 있는 키 h 이상인 사람의 수'에 영향을 주지 않습니다. 따라서 각 사람을 정확히 k번째 위치에 삽입하기만 하면, 그 앞에는 항상 정확히 k명의 키가 h 이상인 사람들이 존재하게 됩니다. 이것이 이 그리디 접근법의 핵심 원리입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
bool cmp(vector <int> a, vector <int> b){
if(a[0] == b[0])return a[1] > b[1];
return a[0] < b[0];
}
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
sort(p.begin(), p.end(), cmp);
vector < vector <int> > ans;
for(int i = p.size()-1; i>=0; i--){
ans.insert(ans.begin() + p[i][1], p[i]);
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
print_vector(ob.reconstructQueue(v));
}
입력
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
출력
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
시간 복잡도 분석
- 정렬 단계: n개의 요소를 정렬하므로 O(n log n)의 시간이 소요됩니다.
- 삽입 단계: 각 삽입 연산은 최대 O(n)의 시간이 걸릴 수 있으며, 이를 n번 반복하므로 O(n²)입니다.
- 전체 시간 복잡도: O(n²)
이처럼 정렬과 순차적 삽입만으로도 조건을 만족하는 대기열을 간단하고 직관적으로 복원할 수 있습니다.