https://school.programmers.co.kr/learn/courses/30/lessons/152995
난이도
Level 3
문제
완호네 회사는 연말마다 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 합니다.
코드
import java.util.*;
class Solution {
public int solution(int[][] scores) {
int[] wh = scores[0];
int whSum = wh[0] + wh[1];
Arrays.sort(scores, (a, b) -> {
if(a[0] != b[0]) return b[0] - a[0];
return a[1] - b[1];
});
int maxScore = 0;
int rank = 1;
for(int[] score : scores){
if(wh[0] < score[0] && wh[1] < score[1]){
return -1;
}
if(score[1] >= maxScore){
if(score[0] + score[1] > whSum){
rank++;
}
maxScore = Math.max(maxScore, score[1]);
}
}
return rank;
}
}
정렬 단계
- 근무 태도 점수(a)를 내림차순, 동료 평가 점수(b)를 오름차순으로 정렬
- 이렇게 정렬하면, 앞에 나오는 사람은 항상 뒤에 나오는 사람보다 근무 태도가 높거나 같고, 같은 경우 동료 평가가 더 낮음
- 따라서 한 번의 순회로 “지금까지 살아남은 사람들 중 동료 평가 최대값”만 관리하면, 이후 직원이 인센티브 대상인지 바로 판단할 수 있음
탈락 여부 판정
순회 중 완호보다 두 점수 모두 높은 직원을 발견하면 완호는 자동 탈락이므로 -1을 즉시 반환
생존자 필터링 및 등수 계산
maxScore에 지금까지 살아남은 사람들의 동료 평가 최고점을 저장- 현재 직원의 동료 평가(b)가
maxScore보다 작으면 이미 앞의 누군가에게 두 점수 중 하나라도 뒤지므로 탈락 - b가 maxScore 이상이면 인센티브 대상이므로, 완호보다 점수 합(a + b)이 크면 rank를 1 증가시켜 완호의 등수를 갱신
- 이후
maxScore를 갱신해 다음 직원 비교에 사용
