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

문제 링크

프로그래머스

문제 설명

완호네 회사는 연말마다 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 합니다.

입출력 예

scores	result
[[2,2],[1,4],[3,2],[3,2],[2,1]]	4

 

문제 풀이

[고려사항]

scores의 최대 길이가 100,000(십만)이므로 시간복잡도를 고려해서 구현해야한다.

*O(n^2)이면 10,000,000,000(백억)으로 보통 코딩테스트 시간을 넘어섬

[알고리즘, 구현방법]

문제만 딱 봤을때는 쉽게 풀 수 있을 줄 알았는데 생각보다 정답인 구현 방법을 생각해내기가 어려워서 시간이 꽤 걸렸다.

혼자서 생각을 못해내서 다른 분들의 아이디어에서 힌트를 얻어서 구현했다.

 

X 1차 생각

완호(인덱스 0)의 석차만 결과로 반환하면 되므로 완호의 점수가 인센티브를 받지 못하는 사원을 제외하고 몇번째에 있는지 확인하면 된다. 대신 완호가 인센티브를 받지 못하는 사원이 될 수도 있으므로 해당 경우도 계산해야한다.

먼저, scores를 순회하면서

1) 근무 태도와 동료 평가 점수 각각의 최솟값을 구한다. => 인센티브를 받지 못하는 사원 확인을 위함

2) 사원별 두 점수의 합을 계산해서 자료구조에 오름차순으로 저장한다. => 석차 확인을 위함

3) 인덱스를 키 값으로 해서 각 사원의 점수 합과 근무 태도 및 동료 평가 점수를 저장한다.

 

여기서 인센티브를 받지 못하는 사원은 두 점수가 모두 어떤 사원들의 점수보다 낮기 때문에 가장 낮은 점수를 가진다. 

그래서 사원별 점수 합을 저장한 자료구조의 맨 앞에 있는 점수를 가진 사원을 찾아 위 조건(두 점수가 최저점)에 부합하는지 확인한다.

부합하면 인센티브를 받지 못하는 사원이 된다.

✅ 2차 생각

모든 사원의 근무 태도 점수(A)를 내림차순으로 정렬하고, 같은 근무 태도 점수인 경우 동료 평가 점수(B)를 오름차순으로 정렬한다.

• 입출력 예시로 들면 [3,2] [3,2] [2,1] [2,2] [1,4] 로 정렬한다.

이 리스트에서 뒤에 나온 사원의 근무 태도 점수(A)는 항상 앞에 있는 사원의 근무 태도 점수보다 작거나 같다.

반면 동료 평가 점수(B)는 오름차순으로 정렬되어있기 때문에, 뒤에 나온 사원의 동료 평가 점수가 앞에 있는 사원의 동료 평가 점수보다 작은 경우, 해당 학생(= 뒤에 나온 사원)보다 두 점수가 높은 사원이 있음이 보장된다.

• 위에서 정렬한 예시로 보면, 인덱스를 0부터 시작할때, 1번 사원과 2번 사원을 비교해보면 된다.
• [3,2] [3,2] [2,1] [2,2] [1,4] 
  • 2번 사원(=뒤에 나온 사원)의 동료 평가 점수(B)는 1로, 1번 사원보다 작다.
  • 그 말은 2번 사원보다 두 점수가 높은 사원인 1번 사원이 있음이 보장된다는 것이다.

앞에 있는 사원과 뒤에 있는 사원을 비교할 때, 근무 태도 점수(A)가 같은 경우가 있으니, 동료 평가 점수(B)가 작다고 해서 둘 다 작다고는 말할 수 없지 않나? 라고 생각이 든다면, 아니다.

근무 태도 점수(A)는 내림차순, 동료 평가 점수(B)는 오름차순이므로 근무 태도 점수(A)가 같은 두 사원은 앞에 있는 사원이 항상 더 큰(정확히는 크거나 같은) 동료 평가 점수(B)를 가지기 때문에 그런 경우는 없다.

 

결국, 정렬한 리스트에서 뒤에 있는 사원의 동료 평가 점수(B)가 앞에 있는 사원의 동료 평가 점수보다 크거나 같을때만 인센티브를 받는 사원이 되는 것이다.

[풀이 과정]

1. 완호 점수와 합계 저장
2. scores 배열을 근무 태도 점수는 내림차순으로, 동료 평가 점수는 오름차순으로 정렬
3. 정렬한 scores 배열을 순회하면서
   • 완호가 인센티브 대상자인지 확인
   • 비교할 사원의 동료 평가 점수가 이전 사원의 점수보다 크거나 같은 경우
     • 완호의 합계보다 큰 경우에만 석차 1 증가

 

정답 코드

import java.util.Arrays;
class Solution {
    public int solution(int[][] scores) {
        // 완호 점수와 합계 저장
        int[] target = scores[0];
		int targetSum = target[0] + target[1];
		// 근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬
		Arrays.sort(scores, (o1, o2) -> {
			return o1[0]!=o2[0] ? o2[0]-o1[0] : o1[1]-o2[1];
		});
		
		int answer = 1;
		int before = 0;
		for (int[] score : scores) {
             // 완호가 인센티브 대상자인지 확인
			if (target[0] < score[0] && target[1] < score[1]) return -1;
            // 현 사원의 동료 평가점수가 이전 사원의 점수보다 크거나 같은 경우만 인센티브 받는 대상
			if (before <= score[1]) {
                // 완호의 합계보다 큰 경우만 석차를 올린다
				if (targetSum < score[0] + score[1]) {
					answer++;
				}
				before = score[1];
			}
		}
       
        return answer;
    }
}