야근 지수

 
문제만 잘 이해했다면 쉬웠던 문제.
다만 생각의 전환만으로도 시간은 2배 가량를, 메모리는 약 5~10배를 대폭 줄일 수 있어,
다짜고짜 풀이가 아닌 수학적인 생각이 얼마나 중요한지 한 번 더 깨닫게 해주는 문제였다.
 

---

 

 
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

---

 

Problem

문제는 설명만 이해한다면 간단하다.
최종적으로 works 배열의 각 숫자 원소들을 제곱하여 더할 건데, 그 값을 최소화 해보라는 문제이며,
최소화 과정은 원소들을 총 n 만큼 빼는 방식으로 진행된다.
 
좀 더 쉽게 설명하면

 
이렇게 결국 값을 계산할 건데,
 

 
이렇게 n을 잘 분배하여 works 들의 원소를 조금씩 빼주고, 그래서 나온 answer 결과가 최소가 되도록 알고리즘을 잘 작성해보라는 문제이다.
 
 
 

Idea

해결 아이디어는 간단하다. 제곱의 값은 지수적으로 값이 증가하기에,
가장 큰 숫자들을 여럿 조금식 줄이는 것이 더 중요하다.
즉, 
 

 
그림처럼 작은 숫자인 1, 2 를 0, 0으로 만들었다고 해도 가장 큰 숫자인 3이 지수적으로 증가하여 정답이 9가 나오는 반면,
큰 숫자인 2, 3을 조금씩 줄여 1, 1 으로 만들면 더 작은 정답 값을 가질 수 있게 된다.
쉽게 얘기하면, 매 순간순간 가장 큰 숫자를 깎아내어야 지수적인 증가를 덜하게 할 수 있다는 의미!
 
따라서, works 의 원소들 중 큰 숫자들의 그룹을 조금씩 빼주는 것이 정답 알고리즘의 핵심이라 볼 수 있겠다.
 
 
 

Solution

여기까지 생각이 닿으면 Max Heap을 당연히 떠올릴 수 있다.
Queue 에 우선 모든 숫자를 때려 넣고, 가장 큰 숫자를 뽑아 1을 빼주고 n을 1만큼 감소 시켜주고.. 를 n이 0이 될 때까지 반복하면 된다.
 
이 과정을 조금 더 직관적으로 설명하자면
 

 
이렇게 현재 남아 있는 원소들 중 가장 큰 숫자를 뽑아 1씩 빼주고, n 도 함께 1씩 빼주면서
n이 0이 될 때까지 반복의 과정을 거치면 되겠다.
 
다만 works 의 모든 원소들을 매번 순회하며 가장 큰 수를 추출하거나, 매번 sort 후에 추출한다면,
works 가 최대 20,000의 길이이고 n이 최대 1,000,000 이므로
최악의 상황에서 20,000 * 1,000,000 의 for 문을 순회할 수 있기 때문에..
이런 상황에서 최적의 시간 복잡도를 가진 Heap 을 이용해야만 시간 초과에서 벗어날 수 있겠다.
 
 
 

Code - 1 (Priority Queue)

Java 의 대표적인 Heap 자료 구조는 PriorityQueue 이다.
사실 PQ 를 이용해서도 간단하게 구현할 수 있지만, 나는 이것만으로는 시간 초과가 나올 수 있겠다 생각하여
밑에 후술할 두 번째 방법을 먼저 적용하긴 했다. (하지만 이 방법만으로도 통과는 됐다)
 

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        
        // Max Heap 을 위해 PriorityQueue + reverseOrder 적용
        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
        
        // queue 에 각 원소 삽입
        long total = 0;
        for(int work : works) {
            total += work;
            que.offer(work);
        }
        
        // 이때 원소의 총합이 n 보다 작다면,
        // 결국 모든 원소가 0이 될 것이므로 계산할 필요 없음
        if(n >= total) {
            return 0;
        }
        
        long answer = 0;
        while(!que.isEmpty()) {
            int num = que.poll();
            answer += num * num;
        }
        
        
        return answer;
    }
}

 

 
// 최종 answer 값 산출을 위한 과정 부분을

원래는 while(!que.isEmpty()) 이 아닌 que.stream().mapToLong(x -> x*x).sum(); 으로 계산 했었는데,
stream 이 while 보다 평균 1~2 ms 가 더 소요되는 것을 확인했다.
알고는 있었지만 확실히 코테에서는 stream 은 지양하는 것이 좋겠다.
 
 
 

Code - 2 (Tree Map)

비슷하게 최대, 최소의 값을 추출할 수 있는 자료구조로 Java 에선 TreeMap 이 있다.
보통 Map 의 key 를 삽입과 동시에 정렬하여 정렬 시간을 단축하기 위해 사용되며, 내부적으로 Red-Black Tree 구조로 이루어져 있다.
 
내가 TreeMap 을 떠올린 이유는
첫 번째로 매번 정렬 및 순회를 하지 않기 위해 당연히 Max Heap 구조를 가질 수 있는 자료구조가 필요했기 때문이고,
두 번째로는 원소의 개수가 무수히 많을 수 있는데, 그 개수만큼 PriorityQueue 에 넣었다가 다시 삽입하고 하는 과정에서 시간 초과가 날 수 있음을 염두에 두었기 때문이다.
 
Idea 부분에서 보았듯 원소들은 서로 같은 값을 가질 수도 있고, 각 원소들의 index 를 기억해야 한다거나 할 필요도 없다.
따라서 나는 TreeMap<Integer, Integer> 을 통해 실제 원소의 값을 key 로, 해당 값인 원소의 개수를 value 로 두고 문제에 접근했다.
 

 
이때 로직은 어차피 가장 큰 숫자를 1씩 빼야 하므로,
가장 큰 숫자를 우선 뽑아서 해당 숫자가 몇 개 있었는지를 n 에서 빼주고,
그 숫자들은 모두 1씩 작아진 상태이므로 key 를 원래 숫자 -1 로 두어 개수만큼 다시 더해주기를 반복하게끔 작성했다.
 

 
나도 TreeMap 을 적극적으로 써본 적이 없어서 어떠한 메서드들이 있는지 몰랐고
막연하게 '당연히 tree 구조니까 가장 큰 수, 가장 작은 수 뽑아주는 메서드가 있겠지..' 라는 생각으로 시작했지만
역시나 있었다. TreeMap 은 lastEntry(), firstEntry() 를 통해 가장 큰, 작은 entry 에 접근할 수도 있고,
 Queue 처럼 pollLastEntry(), pollFirstEntry() 으로 가장 큰, 작은 entry 를 poll 할 수도 있었다.
(참고한 TreeMap 메서드 소개 링크 : https://codevang.tistory.com/134)
 

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        
        // Max Heap + 속도 개선을 통해 TreeMap 적용
        TreeMap<Integer, Integer> worksMap = new TreeMap<>();
        
        // map 에 특정 값의 원소가 몇 개 있는지 삽입
        long total = 0;
        for(int work : works) {
        	total += work;
            worksMap.put(work, worksMap.getOrDefault(work, 0)+1);
        }
        
        // 이때 원소의 총합이 n 보다 작다면,
        // 결국 모든 원소가 0이 될 것이므로 계산할 필요 없음
        if(n >= total) {
        	return 0;
        }
        
        // n 이 0 이 될 때까지 map 에서 원소를 빼고, n 을 1씩 줄임
        Map.Entry<Integer, Integer> biggestEntry;
        while(n > 0) {
        	biggestEntry = worksMap.pollLastEntry();
        	
            // key 는 원소의 값, value 는 원소의 개수가 됨
            int biggestKey = biggestEntry.getKey();
            int biggestValue = biggestEntry.getValue();
            
            
            // n 이 해당 개수 (value) 보다 많거나 같을 때는 모든 원소를 1씩 빼줄 수 있음
            if(n >= biggestValue) {
                n -= biggestValue;
                
                // 모든 원소 (key) 가 1씩 줄었으므로, map 에 key-1 을 value 개수만큼 추가
                worksMap.put(
                    biggestKey-1, worksMap.getOrDefault(biggestKey-1, 0) + biggestValue
                ); 
                    
            // n 이 해당 개수 (value) 보다 작다면 모든 원소를 1씩 빼줄 수 없음
            }else {
                
                // 따라서 남은 n 개 만큼은 1씩 빼주고 map 에 추가,
                // 1이 줄어들지 못한 원소들은 gap 만큼 map 에 추가
                int gap = biggestValue - n;
                worksMap.put(biggestKey, gap);
                worksMap.put(biggestKey-1, worksMap.getOrDefault(biggestKey-1, 0) + n);
                
                // 이 else 분기에 들어왔다면 더이상 남은 n 의 값이 없다는 의미이므로 break
                break;
            }
        }
        
        // map 을 순회하며 최종 answer 값 산출을 위한 과정
        long answer = 0;
        for(Map.Entry<Integer, Integer> entry : worksMap.entrySet()) {
            long key = entry.getKey();
            long val = entry.getValue();
            answer += key * key * val;
        }
        
        
        return answer;
    }
}

 

 
데이터가 많고 시간이 오래 걸린 케이스일수록 단순 PriorityQueue 보다 시간은 약 2배, 메모리는 약 5~10 배의 이점을 본 것을 확인할 수 있다.
 
 
 

End

적용할 로직에 따라서 자료구조 및 알고리즘의 방향성이 달라지고, 그에 따라 시간과 메모리가 달라진다.
따라서 많은 것을 알아두어야 특정 issue 상황에서 여러가지 방법을 떠올릴 수 있고, 최적의 방향을 정할 수 있는 것 같다.
비단 코테만을 위해서가 아닌 앞으로 개발자의 삶을 위해 항상 수학적인 사고를 항상 중요시하자!