[240423] 알고리즘 리부트 54일차 - 프로그래머스 야근 지수 자바

문제를 읽고 먼저 높은 숫자를 줄여나가야 한다고 판단했다. 이를 구현하기 위해 우선순위 큐를 생각해보았지만 같은 작업량을 가진 여러 개의 작업을 n을 하나씩 줄여가며 처리해야 하니 조금 비효율적이라고 생각했다. 이를 보완하기 위해 해시맵을 떠올렸지만 그 안에서 정렬을 매번 수행하느니 트리맵을 사용하자는 결론에 다다랐다. 트리 맵은 자주 사용하지 않아서 메소드가 익숙하지 않아 이건 찾아가며 로직을 구현했다. 만약 남아있는 근무시간과 동일한 작업량을 가진 작업의 수를 비교했을 때 남아 있는 근무 시간(n)이 더 크거나 같다면 해당 작업량의 키를 삭제하고 하나 작은 작업량을 가진 작업 수에 더해주고 n 역시 그 수만큼 줄여준다. 반대로 n이 더 작다면 n 만큼 값을 줄여주고 하나 작은 작업량의 작업 수에 n만큼 더해준 다음 n을 0으로 처리한다.

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        
        // 우선순위 큐, 해시맵?
        
        // 트리맵
        TreeMap<Integer,Integer> tMap = new TreeMap<>();
        
        // works 배열 순회하면서 키는 남은 작업량 값은 해당 작업의 수로 넣기
        for(int w : works) tMap.put(w, tMap.getOrDefault(w,0)+1);
        
        // for(int k : tMap.keySet()){
        //     System.out.println("k: "+k);
        //     System.out.println("값: "+tMap.get(k));
        // }
        
        // 트리맵의 마지막 엔트리를 가져와서 만약 n보다 값이 더 작다면         
        int lastValue = tMap.lastEntry().getValue();
        int lastKey = tMap.lastEntry().getKey();
        
        while(n>0 && !tMap.isEmpty()){    
            lastValue = tMap.lastEntry().getValue();
            lastKey = tMap.lastEntry().getKey();
             
            if(n >= lastValue){
                // 마지막 키 삭제하기(해당 작업량은 없으니까)
                tMap.remove(lastKey);
                // 일했으니 n값 줄여주기
                n-=lastValue;
                // 마지막 엔트리의 하나 작은 키(현재의 마지막 키)의 값에 해당 값만큼 ++ 해주기                             
                if(lastKey-1!=0){
                    tMap.put(lastKey-1, tMap.getOrDefault(lastKey-1,0)+lastValue);
                    //System.out.println(tMap.lastKey());                    
                }                  
            }// 만약 n이 값보다 작다면 n만큼만 처리하기
            else{                
                tMap.put(lastKey, tMap.getOrDefault(lastKey,0) -n);
                //System.out.println(tMap.lastKey());
                tMap.put(lastKey-1, tMap.getOrDefault(lastKey-1,0) +n);
                n = 0;
            }
            
        }             
        
        // treeMap keySet()으로 꺼내서        
        for(int k : tMap.keySet()){
            //System.out.println("k: "+k);
            int value = tMap.get(k);
            //System.out.println("값: "+value);
            // 값을 제곱해 answer에 더해주기            
            answer+=(Math.pow(k, 2))*value;
        }
        
        
        
        return answer;
    }
}

[트리맵]

트리맵은 sortedMap 인터페이스를 내부적으로 상속하고 있다. 해시맵과 달리 오름차순 정렬이 되는 맵이다. 따라서 기본적인 성능은 해시맵에 비해 다소 떨어지지만 정렬 기능이 필요하다면 사용하는 것이 효율적이다. 

만약 정렬 방식을 구체적으로 구현하고자 한다면 아래와 같이 정렬방식을 구현하고 구현체를 함께 선언해주면 된다.

Comparator<Integer> sort = new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2){
            return Integer.compare(o1, o2);
            }
    }

TreeMap<Integer, Integer> treemap = new TreeMAp<>(sort);

- 트리맵의 메서드

1) 값을 넣는 것은 동일하게 put(키, 값) 으로, 키를 삭제하는 것도 remove(키)로, 키와 값 존재여부에 따라 초기값을 설정하거나 값을 변경시키는 것도 getOrDefault(키, 초기값)+변화값으로 동일하다.
2) 트리맵 객체의 키들을 집합체로 리턴하고자 한다면 keySet();을 사용한다.
3) 트리맵 객체의 값들을 Collections의 형채로 리턴하고자 한다면 values();를 사용한다.
4) 트리맵 객체의 첫번째 엔트리(가장 작은 키)를 리턴하고자 한다면 firstEntry();를 사용하고 여기서 .getKey()와 .getValue()를 통해 키와 값을 추출할 수 있다.
5) 위와 반대로 마지막 엔트리(가장 큰 키)를 리턴하고자 한다면 lastKey();를 사용하고 위와 같이 키와 값을 각각 추출 가능하다.
6) 엔트리를 꺼내지 않고 가장 작은 키와 가장 큰 키만을 추출하는 것도 가능하다. firstKey() 또는 lastKey()를 사용한다.
7) 만약 오름차순이 아닌 내림차순으로 정렬해 NavigableMap 객체를 리턴하고자 한다면 descendingMap을 NavigableSet 객체를 리턴하고자 한다면 descendingSet를 사용한다.