[Leetcode/C++] 406_Queue Reconstruction by Height

문제는 다음과 같습니다.

저는 일단 문제를 일단 한 번에 바로 정렬할 수 있는 방법은 없다고 생각했고,
먼저 일차적으로 정렬을 한 뒤, 그 뒤에 이어 재정렬이 필요하다고 생각했습니다.

처음은 정렬은 다음과 같습니다.

• people[i][0]의 원소가 같을 때에는, people[i][1]의 수를 기준으로 오름차순 정렬을 해야 합니다.
• 그리고, 같지 않을 경우에는 people[i][0]의 수를 기준으로 내림차순 정렬을 합니다.
  (왜냐하면, 문제 조건에서 people벡터의 두 번째 원소가 첫 번째 원소 이상의 키를 가진 사람의 수 == 앞에 있는 사람의 수를 나타내기 때문입니다.)

이의 정렬 조건을 함수로 나타내면 다음과 같습니다.

    static bool cmp(vector<int> a, vector<int> b){
        if(a[0]!=b[0]) return a[0]>b[0]; // 내림차순
        else // a[0]==b[0]
            return a[1]<b[1]; // 오름차순
    }

일차적으로 정렬을 마친 뒤에는,
이를 기준으로 재정렬을 해야합니다.

이때에는, 결과벡터에 값을 넣으면서 다음만 비교하면 됩니다.

• 벡터의 마지막 값과 첫번째 원소의 값이 같은 경우 -> 그대로 벡터의 맨 뒤에 넣어줍니다.
• 이와 다른 경우는(벡터의 마지막 값보다 키가 작은 경우) 원소의 두번째 값이 (people[i][1]의 값) 지금까지 정렬된 벡터에서의 순서가 됩니다.
  -> 두번째 값이 벡터 원소의 순서임
  따라서, 해당 순서에 people[i]를 넣어주면 됩니다.

이에 해당하는 코드는 다음과 같습니다.

res.insert(res.begin()+res.people[i][1], people[i])

다음으로 제 전체 코드는 다음과 같습니다.

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        if(a[0]!=b[0]) return a[0]>b[0]; // 내림차순
        else // a[0]==b[0]
            return a[1]<b[1]; // 오름차순
    }
    
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> res;
        
        res.push_back(people[0]);
        
        for(int i=1; i<people.size(); i++){
            if(res.back()[0]==people[i][0]) res.push_back(people[i]);
            else{
                res.insert(res.begin()+people[i][1], people[i]);
            }
        }
        
        
        return res;
    }
};

---

2/8 화요일 복습)

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        if(a[0]!=b[0]) return a[0]>b[0]; // [0]이 다르면 [0] 기준 내림차순
        else return a[1]<b[1]; // [0]이 같으면 [1] 기준 오름차순
    }
    
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        
        vector<vector<int>> res; // 결과벡터
        res.push_back(people[0]);
        for(int i=1; i<people.size(); i++){
            res.insert(res.begin()+people[i][1], people[i]);
        }
        return res;
    }
};