프로그래머스 연습문제 : 인사고과

• 분류: 정렬

코드

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

int solution(vector<vector<int>> scores) {
    int answer = 0;
    int wanho1 = scores[0][0];
    int wanho2 = scores[0][1];
    
    sort(scores.begin(), scores.end(), [](vector<int> a, vector<int> b) {
        if(a[0] > b[0]) return true;
        else if(a[0] == b[0]) return a[1] < b[1];
        else return false;
    });
    
    vector<vector<int>> pass;
    
    int before = scores[0][1];
    for(auto score: scores) {
        if(score[1] >= before) {
            before = score[1];
            pass.push_back(score);
        } else if(score[0] == wanho1 && score[1] == wanho2) return -1;
    }
    
    sort(pass.begin(), pass.end(), [](vector<int> a, vector<int> b) {
        if(a[0] + a[1] > b[0] + b[1]) return true;
        else return false;
    });
    
    for(auto p: pass) {
        answer++;
        if(p[0]+p[1] == wanho1+wanho2) break;
    }
    
    return answer;
}

코멘트

간단해 보였는데 꽤 고전한 문제였다.

두 개의 key로 된 객체가 있는데, 다른 어떤 객체보다 두 key가 모두 더 작은 객체를 걸러내는 것이 핵심이다.

예를 들어 (1, 1), (1, 3), (2, 3) 가 있으면 (1, 1)은 (2, 3)에 의해 제거되고, (1,3)은 제거되지 않는다.

인센티브를 받는 직원을 선별한 후, 두 key의 합에 따라 정렬하고 순위를 구하면 끝이다.

핵심 로직

List<Pair<a, b>>를 a에 대해 내림차순, a가 같으면 b에 대해 오름차순으로 정렬한다.

정렬된 리스트를 선형 탐색하며 b값이 이전까지의 최대 b값보다 큰 경우 최대값을 갱신하고, 해당 객체를 선별한다.

예시: (5, 1), (5, 2), (5, 3), (5, 4), (4, 3), (4, 6), (3, 5), (3, 6), (3, 7), …

위 예시를 보면 (5, 1)부터 (5, 4)까지는 최대값이 1->2->3->4 로 갱신되며 모두 선별된다. 같은 a값을 가지는 것 끼리는 b값에 대해 오름차순했기 때문에 최대값을 갱신시키며 모두 잘 선별할 수 있다.

(4, 3)부터, a값이 이전보다 작아지게 되면 b값이 이전 모든 원소들의 최대 b값보다 작지 않아야 선별된다.

(5, 4)까지 b값의 최대값이 4이므로 (4, 3)은 탈락하고, 다음 원소인 (4, 6)는 선별되고 최대값이 6으로 갱신된다. 그리고 (3, 5)는 탈락하고, (3, 6)과 (3, 7)은 최대값이 5->6->7으로 갱신되며 선별된다.

추가적인 부분

정렬할 때

sort(scores.begin(), scores.end(), [](vector<int> a, vector<int> b) {
        if(a[0] > b[0]) return true;
        else if(a[0] == b[0]) return a[1] <= b[1];
        else return false;
    });

이렇게 <=를 사용하면 segmentation fault가 나는 경우가 있었다. 프로그래머스 질문답변에서 고마운 분의 댓글에 따르면,

sort 의 비교함수는 순약순서 (strict weak ordering) 을 만족해야 하므로 a op a 는 false 가 되어야 하고, a op b 와 b op a 결과가 둘다 true 가 되어서는 안 된다.

라고 한다. 정렬 조건은 꼭 <= 말고 <를 쓰도록 하자.