문제 요약
각 사원마다 근무 태도 점수와 동료 평가 점수가 기록된다. 이 때 다른 임의의 사원보다 두 점수가 모두 낮다면 인센티브를 받을 수 없다. 반대로 두 값의 합이 높은 순으로 석차를 내어 인센티브가 차등 지급된다. 이때 완호의 석차를 구하시오
[ 예시 ]
| scores | result |
|---|---|
| [[2,2],[1,4],[3,2],[3,2],[2,1]] | 4 |
[ 제약 조건 ]
- 1 ≤
scores.length≤ 100,000 scores[i][0]: 근무 태도 점수scores[i][1]: 동료 평가 점수scores[0]: 원호의 점수- 원호가 인센티브를 받지 못하는 경우, -1을 반환한다.
[ 프로그래머스 ]
풀이
- 이런 것도 Greedy 알고리즘이라고 할 수 있나?
(1) scores[0]은 원호의 점수임으로, 미리 초기화한다.
(2) scores 배열을 정렬한다.
- 근무태도 점수
[1]순으로 내림차순 - 만약 근무태도 점수가 같다면, 동료태도 점수
[0]순으로 오름차순 - 이럴 경우, 근무태도를 내림차순으로 정렬했기 때문에 동료 태도만 비교하면, 제외 대상을 판별할 수 있다.
(3) scores 배열을 순환한다.
(3-1) 인센티브를 받지 못하는 경우
- 앞서 이야기 했듯, 근무태도는 이미 내림차순으로 정렬해 이미 앞 사람보다 근무 태도 점수가 낮은 상태이다. 이 상태에서 앞 사람들이 갖는 최대 동료 태도 점수가 낮다면, 제외시켜야한다.
- 이 때, 이 사람이 원호라면 원호는 제외시켜야 하기에
-1를 리턴한다.
(3-2) 인센티브를 받는 경우
- 인센티브를 받지 못하는 경우를 판별할, maxScore를 계산한다.
- 현재 사람의 합이 원호보다 높다면, 해당 사람이 원호보다 석차가 앞임으로
answer을 증가시킨다.
Code
import java.util.*;
import java.math.*;
class Solution {
public int solution(int[][] scores) {
int answer = 0;
int maxScore = 0;
int[] WON = scores[0];
// 근무태도 내림차순
// 같다면 동료태도 오름차순
Arrays.sort(scores, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0]==o2[0])
return o1[1] - o2[1];
return o2[0]-o1[0];
}
});
for(int[] score : scores) {
if (score[1] < maxScore) {
if (score[0] == WON[0] && score[1] == WON[1])
return -1;
} else {
maxScore = Math.max(maxScore, score[1]);
if (score[0] + score[1] > WON[1]+WON[0])
answer++;
}
}
return answer+1;
}
}느낀점
정렬을 이런 식으로 이용하여 하나의 값만을 비교할 수 있음에 놀라움을 금치 못 했다.
세상은 넓고 풀이는 많다 ;-;
이 또한 지나가리라