MATCHORDER self review

[dakyommii]

MATCHORDER self review

1. 해결 시도 과정

작은 점수 차로 이기거나 지는 것이 승리를 많이 하는 방법이라고 생각해 처음에는 한국 레이팅을 기준으로 러시아 레이팅을 하나씩 비교해 가장 점수차가 적은 러시아 레이팅을 찾아 비교해주는 방법을 시도했습니다. 하지만 이 방법으로 하면 최대로 승리할 수도 없고 시간도 오래 걸리고 복잡해지기 때문에 다른 방법으로 오름차순으로 비교해가는 방법을 시도했습니다.

2. 아이디어

승리를 많이 하려면 상대팀을 작은 점수차로 이기는 것이 중요하다는 점을 이용해서 풀이했습니다. 따라서 한국의 레이팅과 러시아의 레이팅을 오름차순으로 정렬한 후 순서대로 비교합니다. 비교할 때 한국 점수가 크면 다음 인덱스로 넘어가서 비교를 계속하지만 러시아 점수가 크면 현재 한국 점수를 맨 뒷 순서로 보내 현재 순서의 러시아 레이팅과 다음 순서의 한국 레이팅을 비교하는 방식을 최종적으로 한국 레이팅이 러시아 레이팅보다 클 때까지 반복하였습니다.

3. 코드 설명

경우에 따라 한국 레이팅을 지우거나 맨 뒤로 보내야하기 때문에 배열 대신 벡터를 사용해 풀이했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> rus;
vector<int> kor;

int N;

승리, 패배 판단하고 승리 횟수 계산하는 메소드

int solution() {

    int cnt = 0;
    
    for (int i = 0; i < N; i++) {
        if (kor[i] >= rus[i]) {  //한국 승리
            cnt++;
        }
        else if(kor[i] < rus[i]) {  //한국 패배
            for (int j = i; j < N ; j++) {
                if (kor[j] >= rus[i]) {
                    cnt++;
                    break;
                }
                else  {
                    kor.push_back(kor[j]);
                    kor.erase(kor.begin()+j);
                }
                
            }
        }
    }
    return cnt;
}

입,출력 부분

int main() {
    int C;
    
    cin >> C;
    
    while (C--) {
        cin >> N;

벡터 초기화

        rus.clear();
        kor.clear();

        int num;
        for (int i = 0; i < N; i++) {
            cin >> num;
            rus.push_back(num);
        }
        
        for (int i = 0; i < N; i++) {
            cin >> num;
            kor.push_back(num);
        }

오름차순 정렬

        sort(rus.begin(), rus.end());
        sort(kor.begin(), kor.end());
        
        cout << solution() << endl;
    }
}

4. 막힌 점 및 개선 사항

컴파일하면 정답이 제대로 나오는데 알고스팟에서 정답 제출을 하면 오답으로 나옵니다. 시간이 초과된 것도 아니라서 알고리즘 부분에서는 잘못된 것이 없는 것 같은데 이유를 모르겠습니다. 비효율적인 부분이 있다면 패배를 판단하는 부분에서 중첩 for문이나 if문을 지저분하게 사용한 부분이라고 생각되는데 그 부분을 다른 코드와 비교해보면서 이유를 찾아야할 것 같습니다.