[프로그래머스 Lv3] 인사고과

문제 설명

• 인사고과

문제 설명

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.

각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

• 1 ≤ scores의 길이 ≤ 100,000
• scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
  • scores[0]은 완호의 점수입니다.
  • 0 ≤ a, b ≤ 100,000
• 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.

---

입출력 예scoresresult

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

4

---

입출력 예 설명

5 번째 사원은 3 번째 또는 4 번째 사원보다 근무 태도 점수와 동료 평가 점수가 모두 낮기 때문에 인센티브를 받을 수 없습니다. 2 번째 사원, 3 번째 사원, 4 번째 사원은 두 점수의 합이 5 점으로 최고점이므로 1 등입니다. 1 등이 세 명이므로 2 등과 3 등은 없고 1 번째 사원인 완호는 두 점수의 합이 4 점으로 4 등입니다.

---

풀이

언뜻 보기엔 단순히 배열을 순회하면서 원호보다 점수가 높으면 순위를 낮추면 될 것 같지만, 중간중간 탈락해버리는 사람들과의 점수 비교도 생기기 때문에, 약간은 더 고민이 필요하다.

풀이 과정은 아래와 같다.

1. scores 배열을 순회하면서
2. 원호보다 인사고과, 동료평가 점수가 모두 높은 사람을 만나면 -1을 반환한다.
3. 그렇지 않다면 원호와 점수를 비교한다. 이 때, 등수 계산에서 제외되는(탈락되는) 사람과는 비교하지 않고 넘어간다. 
4. 비교 결과 점수 합이 원호보다 높은 사람을 만나면 answer(등수)를 1씩 더한다.

아주 간단해 보이는 풀이 과정이다. 그러나 3번 과정에 대해서는 고민할 필요가 있다. 이번에 비교할 사람이 탈락 대상인지 판별하는 방법이 단번에 떠오르지는 않았다.

생각해낸 방법은, scores 배열을 인사교과 점수(이하 A) 내림차순 & 동료평가 점수(이하 B) 오름차순으로 정렬하는 것이다. 

A 내림차순으로 정렬하는 이유는, 배열을 순회하며 비교할 때, 이전에 비교한 사람들은 모두 A가 높았다는 점을 활용하기 위해서다. 그리고 비교해나가면서 B가 가장 높았던 사람의 점수를 기록해놓았다가, 만약 기록해둔 점수보다 낮은 B를 가진 사람을 만났다면, A와 B가 모두 높은 사람이 이전에 있었따는 뜻이기 때문에 때문에 탈락이다.

B 내림차순으로 정렬하지 않은 이유는, A가 같고, B가 높은 사람이 있다고 탈락되면 안되기 때문이다. 내림차순으로 정렬한다면,  A가 같은 사람들 중에서 B가 가장 높은 사람의 B를 먼저 기록해 버리게 된다. 그러면 이후 만나는 모든 A는 같고 B는 낮은 사람들을 탈락시키게 된다. 이는 코드를 보고 이해하는 편이 더 빠를 듯 싶다.

 

---

코드

#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 A = scores[0][0];
    int B = scores[0][1];
    int SUM = A + B;
    scores.erase(scores.begin());
    sort(scores.begin(), scores.end(), comp);
    
    int n = scores.size();
    int maxB = scores[0][1];
    for(int i = 0; i < n; i++)
    {
        int a = scores[i][0];
        int b = scores[i][1];
        int sum = a + b;
        
        //cout << a <<','<<b<<endl;
        
        if(A < a && B < b)
            return -1;
        
        if(b < maxB)
            continue;
        maxB = max(b, maxB);
        
        if(sum > SUM)
            answer++;
    }
    return answer;
}