문제
코드
import java.util.*;
class Solution {
public int solution(int[][] scores) {
int answer = 1;
int[] wanho=scores[0];
Arrays.sort(scores,(a,b)->a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);
int max=scores[0][1];
for(int i=0;i<scores.length;i++){
if(scores[i][1]<max){
if(scores[i][0]==wanho[0]&&scores[i][1]==wanho[1]) return -1;
continue;
}
if(scores[i][0]+scores[i][1]>wanho[0]+wanho[1]) answer++;
max=Math.max(max,scores[i][1]);
}
return answer;
}
}풀이
생각해야 할 것은 두가지이다.
인센티브를 받지 못하는 사람을 제외할 것.
그 중 완호의 석차는 몇등인가.
인센티브를 받지 못하는 경우는 근무 태도 점수와 동료 평가 점수 모두 더 높은 사원이 존재할 때이다.
한명 한명 다 검사해 주기에는 시간복잡도가 n^2이 나오기 때문에 시간초과가 날 것이 뻔하다.
한명씩 검사하지 않고 인센티브 지급 여부를 확인할 수 있는 간단한 방법이 있다.
근무태도 점수에 대해서 내림차순으로 정렬하고, 근무 태도 점수가 같으면 동료 평가 점수로 오름차순 정렬 하는 것이다.
위와 같은 방법으로 문제에서 제시된 예시를 정렬하면,
[3,2], [3,2], [2,1], [2,2], [1,4] 순으로 정렬된다.
앞에서부터 하나씩 인센티브 여부를 확인한다.
이 때, 근무 태도 점수는 확인할 필요 없다. 어차피 앞사람의 점수보다 작기 때문이다.(근무 태도 점수는 내림차순 정렬 되어 있기 때문)
만약 근무 태도 점수가 같다면, 동료 평가 점수에 대해 오름차순 정렬되어 있기 때문에 앞 사람 점수보다 크거나 같다. 그러므로 인센티브 제외 대상이 아니다.
그럼 확인해야 할 것은 동료 평가 점수이다. 어차피 이번에 검사하는 사원의 태도 점수는 앞사람들의 태도 점수보다 작다.
그런데 이 상황에서, 앞사람들의 동료 평가 점수중 가장 높은 점수보다 작다면?
앞에서 검사한 사원중 누군가보다 두 점수 모두가 더 작은 것이다.
위 방법으로 문제를 해결하면,
(1) scores 배열을 근무태도 점수에 대해 내림차순, 동료평가 점수에 대해 오름차순 한다.
(2) 맨 앞부터 한명씩 검사한다.
-
지금 검사하는 사원의 동료평가 점수가 검사했던 사원들 중 가장 높앗던 동료평가 점수보다 작다면 인센티브 제외 대상이 되므로 넘어간다. (continue) , 만약 제외 대상이 완호라면 -1을 return 한다.
-
인센티브 제외 대상이 아니라면, 완호의 점수의 합보다 높은지 검사한다. 높으면 answer++을 해준다. (이 문제는 인센티브를 받는 사람 중, 완호보다 높은 점수 합을 가진 사람 수를 구하는 문제이다.)
결과
나는 처음에 점수 합이 큰 순으로 정렬해서 방법을 찾아보려 했는데, 도저히 생각이 나지 않았다.
그래서 다른 사람 코드를 참고했다.
진짜 근무태도 점수에 대해 내림차순, 동료평가 점수에 대해 오름차순 한다는 생각을 어떻게 하는지 모르겠다.
나는 이걸 이해하는 것도 오래걸렸다.
그리고 나는 이 방법을 적용하고 나서 완호의 등수를 구하기 위해 또 점수 합 순으로 정렬해서 완호의 등수를 구했다.
그런데 또 그럴 필요가 없었다.
그냥 인센티브 지급 여부를 확인하면 완호보다 높은 점수 합인 사람 수를 카운트 해주면 된다.
나는 왜 이런 생각을 못할까 계속 알고리즘을 풀어도 자신감이 붙지 않는다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges
