[Algorithm] Programmers :: 인사고과

https://school.programmers.co.kr/learn/courses/30/lessons/152995

프로그래머스

bool cmp(vector<int>& a, vector<int>& b)
{
    if (a[0] == b[0])
    {
        return a[1] < b[1];
    }
    return a[0] > b[0];
}
 
int solution(vector<vector<int>> scores) {
    int answer = 1;
    vector<int> target = { scores[0][0], scores[0][1] };
    int targetSum = scores[0][0] + scores[0][1];
    int maxSecondNum = 0;
    bool bIsCheck = false;
 
    sort(scores.begin(), scores.end(), cmp);
    
    for (int i = 0; i < scores.size(); ++i)
    {
        if (scores[i][1] < maxSecondNum) // 제거조건
        {
            if (scores[i][0] == target[0] && scores[i][1] == target[1]) // 완호니?
            {
                return -1;
            }
 
            scores[i][0] = scores[i][1] = -1;
        }
 
        maxSecondNum = max(maxSecondNum, scores[i][1]);
 
        if (scores[i][0] + scores[i][1] > targetSum && scores[i][0] != -1)
        {
            ++answer;
        }
    }
 
    return answer;
}

 

주어진 조건에 맞춰서 순위에 반영조차 하지 않을 원소는 제거한 후, 타겟의 순위를 알아내야하는 문제다.

결국 중요한건 순위에 반영하지 않을 원소를 제거해야 하는 것이다.

한 쌍의 두 수가 다른 한 쌍의 두 수보다 작은 경우가 있을 시 삭제한다.

 

두 수를 비교해야하기 때문에 먼저 첫번째 수를 내림차순 해줌으로써 좀 더 간단하게 바꿔준다.

다만, compare 함수를 작성할 때 첫번째 수가 같을 경우에는 두번째 수를 오름차순으로 하게 작성해준다 (매우중요!)

그리고 반복문을 통해 두번째값의 최대값을 갱신하면서 현재 인덱스의 두번째값이 최대값보다 작을 경우 해당 인덱스의 원소는 제거대상이 된다.

즉, 현재 인덱스의 원소의 두번째값보다 큰 값이 이전에 존재하면 제거대상이 된다.

왜냐하면 일단 첫번째값을 기준으로 내림차순을 했기 때문에, 현재 인덱스의  첫번째값과 이전 인덱스의 첫번째 값이 다르다면, 현재 인덱스의 두번째 값이 작다면 무조건 제거대상이 된다.

 

말로 설명하기가 쉽지않긴 한데, 이거는 직접 노트에 숫자 써보면서 해야 이해가 잘된다...

위 문제같은 경우 2중포문으로도 통과되는 경우가 있는 거 같긴 한데, 당연히 위의 코드처럼 O(n)으로 푸는게 시간은 제일 빠르다. 

반복문 돌면서 등수까지 바로 구해버릴 수 있게 코드를 작성도 가능하다.

헷갈리면 그냥 제거할거만 제거한 후에 각 원소의 값을 더한걸 기준으로 오름차순하는 compare함수를 작성 후, sort시키고 구해도 된다.