프로그래머스 - 인사고과 [Java]

이 문제는 그리디 알고리즘을 이용해서 풀었다.

 

scores의 길이 범위가 [1, 100,000] 이므로 O(N log N) 이하의 알고리즘을 생각해야 한다.

 

나의 경우에는 근무 점수를 기준으로 내림차순, 같을 경우 동료 점수 기준으로 내림차순으로 정렬했다.

그 후 delete() 메소드를 통해 기준 미달인 사원을 추출하고, rank() 메소드를 통해 완호의 등수를 매기고 리턴한다.

 

delete 메소드가 굉장히 중요한데, 기본 아이디어는 high라는 변수를 정하고 list를 순회하면서 동료 점수가 더 낮은 경우 삭제하고 만약 높다면 high에 새로 저장하는 것이다.

 

여기서 주의할 점은 점수에 중복이 가능하여 분기문이 추가된다는 것이다. 만약 입력이 [[4, 0], [2, 3], [4, 4], [2, 6]] 일 경우, 정답이 3이 나와야 하는데 high를 변수로 지정하면 4가 나오게 된다.

이는 처음 delete 시 4,4 / 4,0 / 2,6 / 2,3 으로 정렬된 리스트에서 2,3을 제거하지 않게 되어 발생한다. high에 2,6이 저장되어 4,4과의 비교가 이루어지지 않기 때문이다.

 

따라서 high가 변수가 아닌 List로 선언하여 만약 근무 점수가 같을 경우, high 리스트를 쭉 돌며 조건에 부합하는지를 검증하는 절차가 추가되면 정답을 맞출 수 있다.

import java.util.*;
import java.io.*;

class Solution {
    
    List<Node> list = new ArrayList<>();
    
    public int solution(int[][] scores) {
        
        for (int i = 0; i < scores.length; i++) {
            final int index = i;
            final int work = scores[i][0];
            final int cowork = scores[i][1];
            
            list.add(new Node(index, work, cowork));
        }
        
        Collections.sort(list, (e1, e2) -> {
            if (e1.work < e2.work) {
                return 1;
            } else if (e1.work == e2.work) {
                if (e1.cowork < e2.cowork) {
                    return 1;
                }
                return -1;
            }
            return -1;
        });
        
        List<Node> deleted = delete();
        
        if (!wanhoSurvived(deleted)) {
            return -1;
        }
        
        final List<Score> totalScore = makeScore(deleted);
        
        Collections.sort(totalScore, (e1, e2) -> {
            if (e1.score < e2.score) {
                return 1;
            }
            return -1;
        });
        
        return rank(totalScore);
    }
    
    void printList(final List<Node> temp) {
        temp.stream().forEach(e -> {
            System.out.println(e.index + " : " + e.work + " " + e.cowork);
        });
    }
    
    int rank(final List<Score> total) {
        int rank = 0;
        int cnt = 0;
        Score high = null;
        
        for (final Score present : total) {
            // first
            if (high == null) {
                rank = 1;
                cnt++;
                high = present;
            } else {
                if (high.score == present.score) {
                    cnt++;
                } else {
                    rank += cnt;
                    cnt = 1;
                    high = present;
                }
            }
            
            if (present.index == 0) {
                return rank;
            }
        }
        
        return -1;
    }
    
    List<Score> makeScore(final List<Node> temp) {
        List<Score> results = new ArrayList<>();
        
        temp.stream().forEach(e -> {
            results.add(new Score(e.index, e.work + e.cowork));
        });
        
        return results;
    }
    
    boolean wanhoSurvived(final List<Node> temp) {
        for (final Node node : temp) {
            if (node.index == 0) {
                return true;
            }
        }
        
        return false;
    }
    
    List<Node> delete() {
        List<Node> results = new ArrayList<>();
        
        List<Node> high = new ArrayList<>();
        
        for (final Node node : list) {
            // first
            if (high.isEmpty()) {
                high.add(node);
                results.add(node);
                
                continue;
            }
            
            final Node highest = high.get(high.size() - 1);
            
            if (node.work < highest.work) {
                if (node.cowork < highest.cowork) {
                    continue;
                }
                
                results.add(node);
                if (node.cowork > highest.cowork) {
                    high.add(node);
                }
            } else if (node.work == highest.work) {
                if (validate(high, node)) {
                    results.add(node);
                    
                    if (node.cowork > highest.cowork) {
                        high.add(node);
                    }
                }
            }
        }
        
        return results;
    }
    
    boolean validate(final List<Node> high, final Node present) {
        for (final Node node : high) {
            if (node.work > present.work && node.cowork > present.cowork) {
                return false;
            }
        }
        
        return true;
    }
    
    static class Node {
        int index;
        int work;
        int cowork;
        
        Node(int index, int work, int cowork) {
            this.index = index;
            this.work = work;
            this.cowork = cowork;
        }
    }
    
    static class Score {
        int index;
        int score;
        
        Score(int index, int score) {
            this.index = index;
            this.score = score;
        }
    }
}