[C++, 코딩테스트] 우물 안 개구리

 

 

 

#include<iostream>
#include<vector>
#define ALWAYS_WIN 1
#define HAVE_EVER_LOSE -1
#define NO_FRIEND 0

using namespace std;

int main(int argc, char** argv)
{
    int N, M, W;
    cin >> N >> M;
    vector<int> iambest(N, 0);
    vector<int> weight;
    for (int i = 0; i < N; i++){
        cin >> W;
        weight.push_back(W);
    }

    int left, right;
    for (int i = 0; i < M; i++){
        cin >> left >> right;
        int prevLeft = iambest[left - 1];
        int prevRight = iambest[right - 1];
        if (weight[left - 1] > weight[right - 1]){
            iambest[left - 1] = 1;
            iambest[right - 1] = -1;
        }
        else if (weight[left - 1] < weight[right - 1]){
            iambest[right - 1] = 1;
            iambest[left - 1] = -1;
        }
        else {
            iambest[left - 1] = -1;
            iambest[right - 1] = -1;
        }

        if (prevLeft == -1)
            iambest[left - 1] = -1;
        if (prevRight == -1)
            iambest[right - 1] = -1;
    }

    int answer = 0;
    for (int i = 0; i < N; i++){
        if (iambest[i] == 1 || iambest[i] == 0)
            answer++;
    }
    cout << answer << endl;
    return 0;
}

 

 

처음에 iambest 배열은 0으로 초기화 되어있고 0은 친구가 없다는 뜻이다. 그리고 이긴 경우에는 1로 바꾸고 진 경우나 비긴 경우에도 -1로 바꾼다.

친구 관계에 따른 무게 비교를 계속 업데이트하면서 원래 -1이 었으면 이겨서 1로 바뀌었어도 다시 -1로 바꿔서 진 경험을 지우지 못하도록하였다.

 

그래서 모든 친구 관계를 비교하고 나서 iambest에서 1(계속 이긴사람),0(친구가 없는 사람)의 개수를 카운트하면 정답이 나온다.

 

특정 알고리즘이라고 할 필요는 없을 것 같고 비교 결과를 어떻게 잘 정리해서 기록할지를 잘 생각해서 풀면 될 것 같다.