[프로그래머스] 인사고과 - (Java)

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

---

문제 설명

※ 문제에 대한 자세한 설명은 위 링크를 참조해주세요!

일단 해당 문제에서 찾아야 하는 것은 완호의 랭킹입니다. 그리고 이 랭킹을 알기 위해선 인센티브를 받을 수 있는지 여부가 모든 값들에 대해서 알아야 합니다.

현 시점에서 가장 간단하게 생각하면 모든 노드를 돌면서 해당 노드가 인센티브를 받을 수 있는지 여부를 체크하고 완호가 인센티브를 못받는 사람을 제외하고 자기보다 더 큰 사람의 수를 센다면 랭킹을 구할 수 있겠죠.

• 하지만 주어진 scores의 크기가 10만이기에 O(N^2)에 해당하는 알고리즘을 사용할 수 없습니다. 최대 O(NlogN) 정도로 풀어줘야합니다. 이때 잘 생각해보면 자신보다 포인트 총합이 낮은 score에 대해서 인센티브와 관련한 비교를 할 필요가 있을까요?? 없습니다. 그 이유는 나보다 총합이 낮은 경우에 어느 한쪽 포인트가 나보다 높다면 무조건 다른 한쪽 포인트는 내가 높습니다. 그렇기 때문에 인센티브를 못받을지에 대해서 비교할 때 총합 포인트가 낮은 score는 비교하지 않아도 됩니다.

그러면 이렇게 해보면 어떨까요? 총합 포인트에 대해서 내림차순으로 정렬합니다. 그 중 원호를 찾고 원호보다 랭킹이 높은 경우의 사람들 중에 인센티브를 못받는 사람만 빼면 원호의 랭킹이 나오겠죠??

• 하지만 잘 생각해보면 10만개의 score가 있을 때 원호는 꼴찌라고 가정하면 비교해야 하는 부분이 9만9천개가 존재하고 이들에 대해서 모두 비교한다고 가정했을 때 가장한 가장 줄여봐야 N^2/2 이런느낌이겠죠?? 특정 인덱스에서 자신보다 더 높은 인덱스에 대해선 비교할 필요가 없다고 가정했으니까 그 인덱스보다 더 큰 인덱스만 비교한다고 하면 N^2/2 정도 시간복잡도가 나옵니다. 결국은 O(N^2)인거죠.이렇게 해도 시간 제한이 1초라면 풀 수 없습니다.

이 문제는 포인트의 합이 기준이 된다는 점과 이를 이용하여 정렬을 해야한다는 점을 이용하여 문제를 해결할 수 있습니다. 먼저 합이 기준이니까 그 합을 만드는 두 포인트 중 하나를 기준으로 잡겠습니다.

• 저는 태도 점수를 이용해서 기준으로 잡아서 이 태도 점수를 내림차순으로 정렬하겠습니다. 그럼 태도 점수가 높은 것부터 낮은 것까지 차례대로 나오겠죠. 이 때 태도 점수가 같은 경우에 대해서는 어떻게 처리할 수 있을까요?? 만약 똑같이 내림차순으로 정렬한다면 결국 합을 이용해서 정렬한 것과 같겠죠??
  • 이 말이 무슨 말이냐면 결국은 N^2으로 인센티브를 확인할 수 밖에 없다는 말입니다.
• 동료 점수를 오름차순으로 정렬한다면 어떻게 될까요?? 태도 점수가 가장 높으면서 동료 점수가 가장 낮은 score가 맨앞에 올겁니다.
• 이 때 동료 점수만 비교하면서 만약 최대 동료 점수보다 동료 점수가 높다면 최대 동료 점수를 갱신하고 완호의 총합과 비교 후 완호보다 더 큰 score면 갯수를 세어줍니다.
• 만약 최대 동료 점수보다 동료 점수가 낮은 경우라면 어떤 경우일까요?? 저희는 태도 점수를 내림차순으로 동료 점수는 오름차순으로 정렬했으니까 같은 태도 점수인 경우에서는 무조건 동료 점수가 높아지거나 같을 수 밖에 없습니다. 근데 동료 점수가 낮아졌다? 그러면 태도 점수가 이전보다 낮아진 경우고 동료 점수도 자신보다 높은 score가 무조건 있는 경우겠죠? 즉, 인센티브를 받을 수 없는경우가 됩니다.
• 이 때 이 스코어가 완호랑 같다면 완호는 인센티브를 받을 수 없게 됩니다.

이 방법을 이용해서 코드를 짜보겠습니다.

문제 풀이 코드

// 스코어를 태도 점수를 내림차순으로 정렬하고 같다면 동료 점수를 오름차순으로 정렬한다면
// 앞에서부터 for문을 돌 때, 근무 점수는 낮아질 것이고 만약 근무 점수가 같다고 해도 동료 점수는 같거나 무조건 높아집니다.
// 이를 이용해서 해결해보면
// 1. 최대 동료 점수를 가지고 있고 이것보다 높거나 같은 경우라면 최대 동료 점수를 계속 갱신시킵니다.
// 2. 만약 최대 동료 점수보다 낮아진다면 이건 근무 점수가 더 낮은 수로 바뀐 경우가 되고 그 때 동료 점수도 낮아진 것이 되니까
//    그게 완호의 점수랑 같으면 완호는 인센티브를 못받게 되는 겁니다.
// 3. 그리고 위에서 최대 동료 점수를 갱신할 때마다 완호보다 점수가 높은지를 체크하고 높으면 갯수를 올리고 이게 완호보다 더 랭킹이 높은
//    사람을 의미하기에 이를 이용해서 처리를 해봅시다.

import java.util.*;

class Solution {
    private List<Score> scoreList = new ArrayList<>();
    
    public int solution(int[][] scores) {
        initialize(scores);
        Collections.sort(scoreList);
        return getWanhoRank(new Score(scores[0][0], scores[0][1]));
    }
    
    private int getWanhoRank(Score wanho) {
        int maxPeerPoint = 0, ranking = 0;
        for (Score s : scoreList) {
            if (maxPeerPoint > s.peer) {
                if (s.equals(wanho)) {
                    return -1;
                }
            } else {
                maxPeerPoint = Math.max(maxPeerPoint, s.peer);
                if (wanho.getSum() < s.getSum()) {
                    ranking += 1;
                }
            }
        }
        return ranking + 1;
    }
    
    private void initialize(int[][] scores) {
        for (int[] score : scores) {
            scoreList.add(new Score(score[0], score[1]));
        }
    }
}


class Score implements Comparable<Score> {
    int attitude;
    int peer;
    
    public Score(int attitude, int peer) {
        this.attitude = attitude;
        this.peer = peer;
    }
    
    @Override
    public int compareTo(Score s) {
        if (attitude == s.attitude) {
            return peer - s.peer;
        }
        return s.attitude - attitude;
    }
    
    public boolean equals(Score s) {
        return attitude == s.attitude && peer == s.peer;
    }
    
    public int getSum() {
        return attitude + peer;
    }
}

 

---