[C++] 인사고과

[문제]

코딩테스트 연습 - 인사고과 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

1. scores 벡터를 0 index기준으로 내림차순 1 index 기준으로는 오름차순으로 만들자.

2. 정렬된 벡터에서 1번째 index의 max값을 갱신하면서 만일 scores[i][1]이 더 같거나 크고

3. 해당 값이 완호보다 total값이 높다면 answer를 증가시켜주자.

 

해당 코드를 보면 제외시켜주는 부분이 없는데 정답이 되는것에서 의문을 가질 수 있다.

그렇기에 예시로 [[2, 4], [3, 2], [3, 4], [2, 1], [1, 4]] 를 봐보자.

우선 해당 예시에서 정답은 2가 되어야 한다.

 

해당 코드대로 진행이 된다면 처음에는 0번째 index가 가장 높고 1번째 index는 낮은 순서대로 진행이 된다.

즉, 0번째 index가 가장 높은 값들은 모두 total이 2,4보다 높다면 제외가 되지 않고 진행이 된다.

그 이후에 max값은 3,4에서의 4로 넘어가고 이제 뒤의 숫자들은 모두 0번째 index가 3보다 작으니 1번째 index가 4보다 작다면 제외를 시킬 수 있다. 

그렇기에 answer를 증가시키는 것은 total값이 더 높은 3,4이며 2,1의 경우에는 total값을 비교하기 전에 제외가 된다.

[회고]

처음에는 total값이 더 낮은것을 제외하고 벡터에 넣은 뒤에 풀려고 했는데 문제가 생겼었다.

아마 벡터에 넣은 뒤에 다시 total값이 높은 순서대로 정렬하고 벡터에서 완호가 어디 있는지 검색을 하는 방식으로 갔는데 해당 정렬부분에서 문제가 발생했었던 것 같다.

 

잘 생각해보면 따로 제외하는 과정이 없이 더 높은 값만을 추가시키는 방식으로 해결이 가능해서 어렵지 않았던 문제였다.

[코드]

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

using namespace std;

bool cmp(vector<int> a, vector<int> b){    
    if(a[0] == b[0]){
        return a[1] < b[1];
    }
    else{
        return a[0] > b[0];
    }
}

int solution(vector<vector<int>> scores) {
    int answer = 1;
    
    pair<int, int> won;
    won.first = scores[0][0];
    won.second = scores[0][1];
    int won_sum = won.first + won.second;
    
    sort(scores.begin(),scores.end(),cmp);    
    
    int max_score = 0;
    for(int i = 0;i<scores.size();i++){
        if(scores[i][0] > won.first && scores[i][1] > won.second){
            return -1;
        }
        if(max_score <= scores[i][1]){
            if(won_sum < scores[i][0] + scores[i][1]){
                answer++;
            }
            max_score = scores[i][1];
        }
    }
    
    return answer;
}