[JAVA] 프로그래머스 LEVEL3 인사고과

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

프로그래머스

코딩테스트 연습 > 연습문제 > 인사고과

 

난이도: LEVEL3

 

문제 분석

단순히 이중 for문으로 제외할 사원을 찾으면 시간 초과가 발생한다.

 

이유

scores.length 최대 100000  10만 * 10만의 시간 복잡도를 가진다. 

 

정답 코드1

import java.util.*;
class Solution {
    public int solution(int[][] scores) {
        int score1 = scores[0][0]; // 완호 근무 태도 점수 
        int score2 = scores[0][1]; // 완호 동료 평가 점수 
        int sum = score1 + score2; // 완호 종합 점수 
        int cnt = 1;               // 완호 등수 
        
        // 근무 태도 점수 내림차순 / 동료 평가 점수 오름차순 
        Arrays.sort(scores, (o1,o2)->{  
           if(o1[0] != o2[0]) return o2[0] - o1[0];
           return o1[1] - o2[1];
        });
        
        int max = scores[0][1]; // 동료 평가 점수 
        int cur = scores[0][0]; // 근무 태도 점수
        
        TreeSet<Integer> ts = new TreeSet<>(); // 근무 태도 점수가 더 큰 (동료 평가 점수 모음집)
        Set<Integer> temp = new HashSet<>(); // ts 갱신용 
        temp.add(scores[0][1]);
        
        for(int i = 0; i < scores.length; i++){
            boolean safe = true;
            if(cur > scores[i][0]){ // 앞에 케이스 전부가 근무 태도 점수가 더 큰 상황 
                if(max > scores[i][1]) safe = false;
                for(int next : temp){ // ts 갱신
                    ts.add(next);
                }
                temp.clear();
            }
            else if(cur == scores[i][0]){
                temp.add(scores[i][1]);
                Integer result = ts.higher(scores[i][1]); // 근무 태도 점수가 더 큰 동료 점수 모음집 서치 
                if(result != null){
                    safe = false;
                }
            }
            max = Math.max(max, scores[i][1]); // max 항상 갱신 
            
            if(!safe && scores[i][0] == score1 && scores[i][1] == score2) return -1;
            if(safe && sum < scores[i][0] + scores[i][1]) cnt++;
        }
        
        return cnt;
    }
}

 

가장 빠른 풀이 

 

정답 코드2

import java.util.*;
class Solution {
    public int solution(int[][] scores) {
        
        int [][] copy = new int [scores.length][3];
        for(int i = 0; i < scores.length; i++){
            copy[i][0] = scores[i][0];
            copy[i][1] = scores[i][1];
            copy[i][2] = i;
        }
        
        // 정렬 
        Arrays.sort(copy, (o1, o2) -> {
            if(o2[0] != o1[0]) return o2[0] - o1[0];
            return o2[1] - o1[1];
        });
        
        int min = copy[0][0];
        int max_A = copy[0][1]; // min 보다 동일하거나 큰 숫자 중에서 max
        
        int sum = scores[0][0] + scores[0][1]; // 완호 합산 점수 
        int cnt = 1;                           // 완호 등수 
         
        for(int i = 0; i < copy.length; i++){
            boolean safe = true;
            
            if(min > copy[i][0]){
                if(max_A > copy[i][1]) safe = false;
                min = copy[i][0]; // min 갱신 
            }
            else{
                for(int j = 0; j < i; j++){
                    if(copy[j][0] == copy[i][0]) break;
                    if(copy[j][1] <= copy[i][1]) continue;
                    safe = false;
                    break;
                }
            }
            if(max_A < copy[i][1]) max_A = copy[i][1];
            
            if(safe && sum < copy[i][0] + copy[i][1]) cnt++;
            if(!safe && copy[i][2] == 0) return -1;
            
        }
        return cnt;
    }
}

 

정답 코드3

import java.util.*;
class Solution {
    public int solution(int[][] scores) {
        
        int [][] scores2 = new int [scores.length][3];
        for(int i = 0; i < scores.length; i++){
            scores2[i][0] = scores[i][0];
            scores2[i][1] = scores[i][1];
            scores2[i][2] = i;
        }
        
        Arrays.sort(scores2, (o1, o2) -> {
           if(o1[0] != o2[0]) return o2[0] - o1[0];
           return o2[1] - o1[1];
        });
        
        int memo = scores[0][0] + scores[0][1];
        int cnt = 1;
        
        TreeSet<Integer> treeSet = new TreeSet();
        treeSet.add(scores2[0][1]);
        
        int min = scores2[0][0];
        
        for(int i = 0; i < scores2.length; i++){
           boolean safe = true;
           if(min > scores2[i][0]){ // 트리셋에 누적된 데이터 활용 가능 
               Integer result = treeSet.higher(scores2[i][1]);
               if(result != null){
                   safe = false;
               }
               min = scores2[i][0];
           }
           else{
              for(int j = 0; j < i; j++){
                   if(scores2[i][0] == scores2[j][0]) break;
                   if(scores2[i][1] < scores2[j][1]){
                       safe = false;
                       break;
                   }
              }  
           }
           treeSet.add(scores2[i][1]); 
           
           if(scores2[i][2] == 0 && !safe) return -1; // 인센티브     
           if(safe && (scores2[i][0] + scores2[i][1]) > memo) cnt++;  
        }
        return cnt;
    }
}

 

정답 코드2 정답 코드3에서 개선 트리셋 활용 → 최댓값 

 

정답 코드4

import java.util.*;
class Solution {
    public int solution(int[][] scores) {
        int score1 = scores[0][0]; // 완호 근무 태도 점수 
        int score2 = scores[0][1]; // 완호 동료 평가 점수 
        int sum = score1 + score2; // 완호 종합 점수 
        int cnt = 1;               // 완호 등수 
        
        // 근무 태도 점수 내림차순 / 동료 평가 점수 오름차순 
        Arrays.sort(scores, (o1,o2)->{  
           if(o1[0] != o2[0]) return o2[0] - o1[0];
           return o1[1] - o2[1];
        });
        
        int max   = scores[0][1]; // cur 보다 같거나 큰 근무 태도 점수중 동료 평가 점수 max
        int max_2 = 0;            // cur 보다 큰 근무 태도 점수중 동료 평가 점수 max
        int cur = scores[0][0]; // 근무 태도 점수
        
        Set<Integer> temp = new HashSet<>(); // max_2 갱신용 
        temp.add(scores[0][1]);
        
        for(int i = 0; i < scores.length; i++){
            boolean safe = true;
            if(cur > scores[i][0]){ // 앞에 케이스 전부가 근무 태도 점수가 더 큰 상황 
                if(max > scores[i][1]) safe = false;
                for(int next : temp){ // max_2 갱신
                    max_2 = Math.max(max_2, next);
                }
                temp.clear();
            }
            else if(cur == scores[i][0]){
                temp.add(scores[i][1]);
                if(max_2 > scores[i][1]){ // 근무 태도 점수가 더 큰 동료 점수 모음집 서치 
                    safe = false;    
                } 
            }
            max = Math.max(max, scores[i][1]); // max 항상 갱신 
            
            if(!safe && scores[i][0] == score1 && scores[i][1] == score2) return -1;
            if(safe && sum < scores[i][0] + scores[i][1]) cnt++;
        }
        
        return cnt;
    }
}

 

정답 코드1에서 treeSet 사용 x 버전