올림픽(백준 8979)

(출처) https://www.acmicpc.net/problem/8979

우선순위 큐로 Ranking을 계산하며 정답을 구했는데..

정해진 규칙에 맞게 주어진 나라의 순위표를 작성하는 문제.

결론부터 말하자면 나는 우선순위 큐와 재귀를 이용해서 문제를 풀었다.

최초에는 금메달부터 시작하여 금메달 개수로 우선순위를 매겨 각 나라를 큐에 집어넣는다.

이후 큐에서 나라를 하나씩 꺼내가면서 찾고자 하는 나라를 발견할 때까지 계속 랭킹을 계산해 가는 방식이다.

만약 찾고자 하는 나라를 발견했는데 금메달 개수가 동률인 여러 나라들이 존재하는 상황이라면, 동률인 나라들만 모아서 다시 한번 재귀를 돌려 이번엔 은메달을 검사하고, 또 동률이 나온다면 마찬가지로 재귀를 돌려 동메달을 검사하는 식으로 결과를 구해냈다.

위 로직대로 구현하여 정답 처리를 받긴 했지만 코드를 짜면서도 진짜 이렇게 푸는 게 맞을까? 구현이 너무 지저분하다는 느낌이 머릿속에서 떠나질 않았다.

그래서 문제를 풀고 다른 분들의 풀이를 찾아봐보니 많은 분들이 그냥 간단히 정렬함수를 만들어 문제를 풀었더라.

그걸 보면서 난 뭣하러 우선순위 큐에다 굳이 재귀까지 돌려가면서 복잡하게 구현했을까 그런 생각이 들기도 하고.. 역시 아직 기초적인 경험부터가 많이 부족한 것 같다는 걸 느꼈다.

코드(우선순위 큐)

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef priority_queue<pair<int, vector<int>>> PQ;
int ranking = 0;
PQ pq;
PQ recur_pq;
int N, K;


void get_ranking(int recur) {
    if(recur == 3) return;
    int this_medal = pq.top().first;
    vector<int> this_nation = pq.top().second;
    bool nation_flag = false;
    if (this_nation.back() == K) nation_flag = true;
    if(nation_flag && pq.size() == 1) return;

    recur_pq.push(pair<int,vector<int>>(this_nation[recur], this_nation));
    pq.pop();

    while(!pq.empty()){
        int next_medal = pq.top().first;
        vector<int> next_nation = pq.top().second;
        // 등수가 확실하게 갈리는 지점을 발견
        if(this_medal != next_medal) {
            // 내가 원하는 나라를 발견하지 못한 상태라면 랭킹 계산 후 계속 찾기
            if(!nation_flag) {
                //랭킹 계산 후 pq2 clear
                ranking += recur_pq.size();
                recur_pq = PQ();
            }
            // 원하는 나라를 발견한 상태라면 다시 세부 등수확인을 위해 루프 탈출
            else {
                pq = recur_pq;
                recur_pq = PQ();
                get_ranking(++recur);
                return;
            }
        }
        // 등수가 구분이 안되는 경우 현재 발견한 나라를 저장
        if (next_nation.back() == K) nation_flag = true;
        recur_pq.push(pair<int,vector<int>>(next_nation[recur], next_nation));
        this_nation = next_nation;
        this_medal = next_medal;
        pq.pop();
    }

    if(!recur_pq.empty()) {
        pq = recur_pq;
        recur_pq = PQ();
        get_ranking(++recur);
    }
}

int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        pq.push(pair<int,vector<int>>(b,{c,d,a}));
    }
    get_ranking(0);
    cout << ranking + 1 << "\n";
    return 0;
}

코드 (정렬방식으로 다시 짜본 코드)

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int K;

bool compare(vector<int> &a, vector<int> &b) {
    if(a[0] > b[0]) return true;
    else if(a[0] == b[0]){
        if(a[1] > b[1]) return true;
        else if(a[1] == b[1]) {
            if(a[2] > b[2]) return true;
            else if(a[2] == b[2]) {
                if(a[3] == K) return true;
            }
        }
    }
    return false;
}

int main(){
    int N;
    cin >> N >> K;
    K--;
    vector<vector<int>> list(N);
    for(int i = 0; i < N; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--;
        list[a] = {b, c, d, a};
    }
    sort(list.begin(), list.end(), compare);
    int ranking = 1;
    for(vector<int> l : list) {
        if (l[3] == K) break;
        ranking++;
    }
    cout << ranking << endl;
}

기억하고 싶은 점

정렬함수를 따로 구현하여 정답을 제출했는데 이상하게 오류 날 건덕지가 없는 것 같은데 자꾸 런타임 오류로 말썽을 부리더라.

그래서 한번 찾아보니 정렬함수를 만들 때 Strict Weak Ordering 규칙 문제와 관련된 오류가 많이 발생하곤 하니 주의해야 된다는 사실을 알아냈다.

Strict Weak Ordering 에 관한 글(링크)