[백준 9017] - 크로스 컨트리 c++

 

[백준 9017] - 크로스 컨트리 c++

 

문제

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

9017번: 크로스 컨트리

난이도 - 실버3

접근 방법

구현 문제라고 써져 있지만, 정렬 문제에 더 가깝다고 생각했다.

처음엔 쉬워보였는데, 막상 구현하려니 조건이 까다로웠다.

 

deleted_arr를 둬서 6명의 팀원이 없는 팀들을 제거한 상태를 저장하려고 했는데, 배열의 특정 원소를 삭제하는 함수를 몰랐다.

그래서 6명의 팀원이 존재하는 팀만 골라내어 deleted_arr에 push_back해줬다.

 

delete_arr를 이용해서 result를 생성했다. result에는 team, four, five, six, cnt를 한 원소에 담았다. 비교할 때 편하게 하기 위해서  four, five, six를 따로 선언했다. cnt는 four, five, six를 생성하기 위해 필요했다.

처음엔 four, five, six를 따로 배열로 선언할까 고민을 했지만, 그렇게 구현하는 것 보다 이게 나아보였다. 

 

코드

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

using namespace std;

struct score{
    int team;
    int four;
    int five;
    int six;
    int cnt;
};

vector<score> make_result(vector<int> deleted_arr) {
    vector<score> result;

    for (int i=0;i<deleted_arr.size();i++) {
        bool flag = false;
        for (int j=0;j< result.size();j++) {
            if (result[j].team == deleted_arr[i] ) {
                result[j].cnt++;
                if (result[j].cnt <= 4) result[j].four += i + 1;
                if (result[j].cnt == 5) result[j].five = result[j].four + i + 1;
                if (result[j].cnt == 6) result[j].six = result[j].five + i + 1;
                flag = true;
                break;
            }
        }
        if (!flag) {
            score temp; temp.four = 0; temp.five = 0; temp.six = 0; temp.cnt = 1;
            temp.team = deleted_arr[i];
            temp.four = i + 1;
            result.push_back(temp);
        }
    }

    return result;
}

bool comparator (score a, score b) {
    if (a.four == b.four) {
        if (a.five == b.five) return a.six < b.six;
        else return a.five < b.five;
    } else {
        return a.four < b.four;
    }
}

int main () {

    int T;
    cin >> T;
    for (int tc = 0;tc<T;tc++) {
        int n; cin >> n;
        vector<int> arr(n);
        vector<int> deleted_arr;
        vector<score> result;
        
        for (int i=0;i<n;i++) {
            cin >> arr[i];
        }
        int point = 0;
        for (int i=0;i<n;i++) {
            int cnt = 0;
            for (int j=0;j<n;j++) {
                if (arr[i] == arr[j]) {
                    cnt++;
                }
            }
            if (cnt >= 6) {
                deleted_arr.push_back(arr[i]);
            }
        }

        result = make_result(deleted_arr);
        sort(result.begin(), result.end(), comparator);

        cout << result[0].team << endl;
    }

    return 0;
}

 

 

개선할 점

struct를 사용하지 않고 구현하려고 했지만, 많이 애를 먹었다.

알고리즘 문제 풀이에서 struct를 사용해본 건 처음인데, 앞으로는 많이 써먹으면 좋을 거 같다. 다만 코드가 조금 복잡해진다.