[프로그래머스LV3] 인사고과(C++)

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

프로그래머스

 

쉬운듯 하면서도 까다로운 문제였다.  N이 10만으로 N^2 하면 TLE 이므로 최적화가 필요한 문제였다.

처음엔 근무태도, 동료평가를 각각 sort한 배열을 만들었는데 이렇게하면 안된다. 결국은 O(N^2)의 시간이 필요하게 되기 때문이다.

 

문제의 골자는 다음과 같다. 

 

1. 이 사람이 인센티브를 받을 수 있는가? -> 모든 사람에게 둘 다 밀리지는 않는가?

2. 그래서 원호의 순위는?

 

그래서 이 문제는 sort를 통해 근무태도, 동료평가 중 하나만 평가하면 되도록 최적화하는 것이 핵심이다. 

[[2,2],[1,4],[3,2],[3,2],[2,1]]

문제에서 준 예제를 근무 태도에 대해서는 내림차로, 동료평가에 대해서는 오름차로 정렬한다. 그렇다면

 

3,2

3,2

2,2

2,1

1,4

 

이렇게 정렬될 것이다. 우린 이제 근무 태도에 대해서는 딱히 신경쓸 필요가 없다 왜냐하면 어차피 근무태도는 나보다 나은 사람이 존재하기 때문이다. 이제 신경쓸 것은 과연 내 위에 나보다 동료평가도 좋은 사람이 있을까? 를 고민해야한다. 그래서 maxValue 를 하나 만들어서 i번째까지 탐색했다고할 때, 그 때까지의 최대 동료평가 점수를 저장하고 있어야한다. 

 

위를 예로 들면 2, 1 을 검사할 때 지금까지 최대 동료평가 점수는 2였다. 그러니까 2, 1 은 인센티브를 받을 수 없다고 판단한다.

 

또한 순위가 1 1 3 3 5 이런식으로 된다고 해도 결국은 원호보다 점수합이 높은 사람이 몇명인지와 같은 문제이기 때문에 복잡하게 실제 순위를 구하지말고 원호보다 나은 사람이 몇명인지만 새면 된다.

 

아주 코딩테스트스러운 문제였다. 나중에 다시 한 번 풀어보자

 

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

bool comp(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;
    int ansX = scores[0][0];
    int ansY = scores[0][1];
    
    sort(scores.begin(), scores.end(), comp);
    
    int maxValue = scores[0][1];
    
    for(vector<int> v : scores){
        if(ansX < v[0] && ansY < v[1]) return -1;
        if(v[1] < maxValue) continue;
        if(ansX + ansY < v[0] + v[1]) answer++;
        
        maxValue = max(maxValue, v[1]);
    }
    
    return answer;
}