[2차원 배열 서로 다른 기준으로 정렬] 인사고과

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

프로그래머스

💡문제 분석 요약
[근무태도점수, 동료평가점수]
점수 합 = 근무태도 점수 + 동료 평가 점수

1. 기준 미달 사원 제외
2. 제외하고 남은 사원 점수 합 내림차순 정렬하여 등수 매기기

3. 정렬할 때, 완호의 점수 위치가 바뀌므로 원호의 점수를 따로 저장

 

💡알고리즘 설계

1. 정렬하기

   근무 태도 점수로 일단 내림차순을 하고, 근무 태도 점수가 동일할 경우, 동료 평가 점수로 오름차순 정렬한다.

   Arrays.sort(scores, (a,b) -> a[0]==b[0] ? a[1]-b[1] : b[0]-a[0]); 

   a-b : 오름차순     0 : 근무 태도 점수 
   b-a : 내림차순     1:  동료 평가 점수
  // 근무태도 점수가 같을 경우, 동료평가 점수 기준으로 오름차순 정렬
  // 근무태도 점수가 다를 경우, 근무태도 점수를 기준으로 내림차순

 

 

2. 인센티브 못 받을 사람 거르기

근무 태도 점수는 내림차순으로 정렬된 상태이다. 따라서 scores 속 사람들은 근무 태도 점수가 최대값과 같은 사람을 제외하면 위의 사람보다 근무 태도 점수가 작다. 그렇기 때문에 동료 평가 점수만 비교하면 된다.

 

만약 어떤 사람이 자기 위에 사람보다 동료 평가 점수가 작다면 두 점수 모두 작은 것이기 때문에 지워주면 된다. 동료 평가 점수는 오름차순 정렬이기 때문에 바로 위 사람만 비교하면 된다.

예를들어, 아래와 같이 정렬된 경우 (2,1) 의 1점은 위 (3,2)의 2점보다 낮아 제외 대상이다.

3 2 3 2 2 1 2 2 1 4

예시

 

하지만 원호가 걸러지는 경우를 따져줘야 한다.
그래서 1단계 전에 원호의 점수를 int[] wh 라는 배열에 미리 저장해둔다.

변수 maxPeerScore는 현재까지 본 동료 평가 점수 중 최대값이다. 최대값만 필요한 이유는 자기보다 두 점수가 모두 높은 사람 딱 한명만 찾으면 되기 때문이다.

 

만약 걸러지지 않았다면 위의 사람보다 동료 평가 점수가 높았다는 것이므로 maxPeerScore 를 갱신하고,

걸러진다면 그 사람이 원호인지 확인한다
원호라면 -1을 반환하고
아니라면 그 사람의 점수를 모두 -1로 바꿔준다 -> 후에 (근무태도 점수 + 동료평가 점수)를 음수로 만들어서 정렬 했을때, 맨뒤로 가게 만들기 위해서이다.

 

 

3. 등수 구하기

Arrays.sort(scores, (a,b) -> (b[0]+b[1]) - (a[0]+a[1]));  

: 합(근무태도 점수 + 동료평가 점수)을 기준으로 내림차순 정렬

 

위처럼 정렬할 경우, 인센티브 제외 대상자는 두 합이 음수이므로 맨 뒤로 가게 되어, 등수를 매기는데 제외된다.

 

 

💡시간복잡도
제한사항
1<= scores의 길이<=100,000

1. 정렬 (Sort):
   • Arrays.sort() 메서드를 사용하여 두 번 정렬이 수행된다.
   • 정렬 알고리즘에 따라서 Arrays.sort()의 시간 복잡도가 다를 수 있다. 일반적으로 자바에서 사용되는 정렬 알고리즘은 퀵 정렬(Quick Sort)이며, 이 경우에는 평균적으로 O(N log N)의 시간 복잡도를 갖는다. 하지만 최악의 경우에는 O(N^2)의 시간 복잡도를 가질 수 있다.
   • 첫 번째 정렬은 두 번째 열(동료 평가 점수)을 기준으로 내림차순으로 정렬됩니다. 이때의 시간 복잡도는 O(N log N)이다.
   • 두 번째 정렬은 행마다의 합을 기준으로 내림차순으로 정렬됩니다. 이때의 시간 복잡도 역시 O(N log N)이다.
   • 따라서 정렬 작업의 총 시간 복잡도는 O(N log N)이다.
2. 반복문:
   • 첫 번째 반복문은 행렬을 순회하며 원호의 점수와 동일한지, 그리고 동료 평가 점수가 원호보다 낮은지 확인합니다. 이 반복문의 시간 복잡도는 O(N)입니다.
   • 두 번째 반복문은 다시 정렬된 행렬을 순회하여 등수를 계산합니다. 이 반복문의 시간 복잡도 역시 O(N)입니다.
   • 따라서 반복문 작업의 총 시간 복잡도는 O(N)입니다.

따라서 전체 코드의 시간 복잡도는 정렬과 반복문 작업의 복잡도를 합산하여 다음과 같습니다.

O(NlogN)+O(N)+O(N)=O(NlogN)

따라서 이 코드의 시간 복잡도는 O(NlogN)입니다.

100,000 * log(100,000) 는 평균적으로 약 500,000 연산 횟수가 나올 수 있다

 

💡코드

import java.util.*;
class Solution {
    public int solution(int[][] scores) {
        int answer = 1; //리턴하는 값은 등수 이므로 1부터 시작
        int[] wonho={scores[0][0],scores[0][1]};    // 원호점수
        
        Arrays.sort(scores, (a,b) -> a[0]==b[0] ? a[1]-b[1] : b[0]-a[0]);
        
        int maxPeerScore = scores[0][1];
        
        for(int i=0;i<scores.length;i++){
            if(scores[i][1]<maxPeerScore){  // 위보다 동료 평가 점수가 작아 걸러지면
                if(scores[i][0] == wonho[0] && scores[i][1] == wonho[1]){           // 원호인지 확인
                    return -1;
                }else{          //원호가 아닐경우
                     scores[i][0] = -1;
                     scores[i][1] = -1;
                }
            }
            else{
                maxPeerScore = scores[i][1];
            }
        }
        
        Arrays.sort(scores, (a,b) -> (b[0]+b[1]) - (a[0]+a[1]));    //합을 기준으로 내림차순 정렬
        
        for(int i=0;i<scores.length;i++){
            if(scores[i][0]+scores[i][1] > wonho[0]+wonho[1]){
                answer++;
            }
            else{
                break;
            }
        }
        // for(int i=0;i<scores.length;i++){
        //     System.out.println(scores[i][0]+" "+scores[i][1]);
        // }
        
        return answer;
    }
}

 

💡느낀점, 기억해야 할 점

1. 무언가 크기나 길이를 비교해야 하는 경우, 정렬을 하면, 더 간단해질 수 있다.

: 한가지가 아닌 2가지의 기준을 갖고 비교해야 하는 경우 일단 한쪽을 정렬 한 후,

   남은 한쪽을 비교해가며 찾는 방법도 잊지말것

 

2. 특히 2차원 배열인 경우, 정렬기준이 2가지가 가능해, 꼭 두가지 모두 오름차순, 내림차순으로 통일할 필요가 없다.

     한쪽은 오름차순, 다른 한쪽은 내림차순 정렬을 시킬 경우도 있으니 다양하게 생각해 보자