[leetcode 406] Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

 

Example

Input: [[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]]

 

- 0 th는 키, 1th는 앞에 있는 사람 중에 키가 크거나 같은 사람의 수

 

 

풀이 :

-sort 사용: 소트를 하되 1th 열로 오름차순 정렬. 0th 열로는 내림차순

7-0 7-1 6-1 5-0 5-2 4-4

- 소트한 배열을 기준으로 answer.begin + people[i][1] 에 인서트- 키 순으로 내림차순 이므로 이미 큰 키가 정렬되있기 때문에 작동.7-07-0 7-17-0 6-1 7-15-0 7-0 6-1 7-1 ...

 

#include <algorithm>
class Solution {
    static bool cmp(const vector<int> &a, const vector<int> &b){
        if(a[0] == b[0]){
            return a[1] < b[1];
        }
        return a[0] > b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> answer;
        
        sort(people.begin(), people.end(), cmp);
        for(int i=0; i<people.size(); i++){
            answer.insert(answer.begin() + people[i][1], people[i]);
        }
        return answer;
    }
};