[BOJ] 7568 덩치

https://www.acmicpc.net/problem/7568

7568번: 덩치

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

sorting

 

---------------------------------------------------풀이----------------------------------------------------

 

x,y값과 원래의 인덱스 값을 저장하는 structure Man을 만들었다.

Man을 x값을 기준으로 내림차순으로 정렬하고,

정렬된 Man들을 앞에서부터 보면서

i번째 Man의 앞에 있는 0~i-1번째 Man 중 x값과 y값이 더 큰 Man의 수+1을 정답의 idx에 저장해주었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>

using namespace std;

typedef struct{
    int x, y;
    int idx;
}Man;

bool cmp(Man a, Man b){
    return a.x > b.x;
}

// 각 사람의 덩치 등수를 계산해라.(x,y 다 나보다 큰 사람 수 + 1)
int main(void){
    FASTIO;
    Man m;
    int N;
    cin >> N;
    vector<Man> v;
    for(int i = 0; i < N; i++){
        cin >> m.x >> m.y;
        m.idx = i;
        v.push_back(m);
    }
    // 첫 번째 값 기준 정렬
    sort(v.begin(), v.end(), cmp);
    vector<int> ranks(N);
    for(int i = 0; i < N; i++){
        int rank = 1;
        // x값이 자신보다 큰 사람(앞에 있는 사람) 중에서 y값이 자신보다 큰 사람의 수
        for(int j = 0; j < i; j++){
            if(v[j].x > v[i].x && v[j].y > v[i].y){
                rank++;
            }
        }
        ranks[v[i].idx] = rank;
    }
    for(int i = 0; i < N; i++){
        cout << ranks[i] << " ";
    }
    cout << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

x값 기준으로 정렬된 상태에서, x값이 같은 사람에 대한 예외처리를 해주지 않아 틀렸었다.

예를 들어, (2,10), (2,9), (2,2)이면 x값은 모두 같으므로 모두 등수가 1등이 되어야하는데,

x값 기준 정렬된 상태에서 앞에 있는 값 중 y값이 큰 값을 구했더니

(2,9)는 2등, (2,2)는 3등이 되는 오류가 있었다.

따라서, x값으로 정렬된 상태여도 x값이 더 큰지 체크하는 부분을 추가하였다.