C++의 높이별 대기열 재구성

대기열에 서 있는 무작위 목록이 있다고 가정해 보겠습니다. 각 사람이 한 쌍의 정수(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]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 다음 비교 전략에 따라 주어진 배열 정렬
  • a[0] =b[0]이면 a[1]> b[1]을 반환하고, 그렇지 않으면 a[0]
• 로 불리는 하나의 벡터 생성
• 주어진 배열의 범위 크기가 0까지인 i의 경우
  • ins 배열에 ans + p[i, 1], p[i]의 첫 번째 요소 삽입
• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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]]