[1일 1알고] 인사고

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

프로그래머스

 

오늘은 정렬에 관련된 문제입니다.

 

근무 태도, 동료 평가를 어떤 사원과 비교해 둘 다 저조한 사원이 있다면 인센티브를 받을 수 없습니다.

그리고 문제의 목표는 완호(scores[i])의 석차를 아는 것입니다.

 

따라서 인센티브를 받을 수 없는 사원을 거른 후 완호의 석차를 별개로 다시 구해야할 것입니다.(완호가 걸러지는 경우는 -1)

 

사원을 필터링하기 위해서는 일단 하나의 조건을 통해 내림차순으로 정렬 후 나머지 조건은 반대로 오름차순으로 정렬해 최댓값만 가진채 순회하면 필터링될 것입니다.

    sort(scores.begin(), scores.end(), [](const vector<int>& a, const vector<int>& b)
    {
        if (a[0] == b[0])
            return a[1] < b[1];

        return a[0] > b[0];
    });

    int maxPeer = 0;
    vector<pair<int, int>> goodWorkers;
    for (int i = 0; i < N; ++i)
    {
        int work = scores[i][0];
        int peer = scores[i][1];

        if (peer < maxPeer)
        {
            if (work == targetWork && peer == targetPeer)
                return -1;
        }
        else
        {
            goodWorkers.push_back({ work, peer });
            maxPeer = max(maxPeer, peer);
        }
    }

전체 코드의 일부입니다.

maxPeer를 설정한다면 work는 이미 정렬되어있으므로 필터링이 가능하고 peer로도 필터링이 가능하게 됩니다.

---

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

using namespace std;

// 1. 근무 태도, 2. 동료 평가
// 어떤 사원 보다 두 점수가 모두 낮은 경우가 있다면 인센티브 x
// 아니라면 두 점수의 합이 높은 순으로 석차를 매김
// 동석차 처리는 1, 2, 2, 4 와 같은 방식

int solution(vector<vector<int>> scores) {
    int answer = 0;
    int N = scores.size();

    int targetWork = scores[0][0];
    int targetPeer = scores[0][1];

    sort(scores.begin(), scores.end(), [](const vector<int>& a, const vector<int>& b)
    {
        if (a[0] == b[0])
            return a[1] < b[1];

        return a[0] > b[0];
    });

    int maxPeer = 0;
    vector<pair<int, int>> goodWorkers;
    for (int i = 0; i < N; ++i)
    {
        int work = scores[i][0];
        int peer = scores[i][1];

        if (peer < maxPeer)
        {
            if (work == targetWork && peer == targetPeer)
                return -1;
        }
        else
        {
            goodWorkers.push_back({ work, peer });
            maxPeer = max(maxPeer, peer);
        }
    }

    sort(goodWorkers.begin(), goodWorkers.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first + a.second > b.first + b.second;
    });

    int rank = 0;
    int prevScore = -1;
    int accum = 1;
    for (auto& goodWorker : goodWorkers)
    {
        int work = goodWorker.first;
        int peer = goodWorker.second;
        int score = work + peer;
        if (score == prevScore)
            ++accum;
        else
        {
            rank += accum;
            accum = 1;
            prevScore = score;
        }

        if (work == targetWork && peer == targetPeer)
            return rank;
    }

    return answer;
}

전체 코드입니다.

 

생각해보니 완호의 등수만 필요하기 때문에 별도의 정렬없이 원 루프 안에서 모두 처리도 가능하겠네요