Today's Algorithm(2018-12-04)

programmers 더 맵게

문제 자체가 어렵진 않았는데 저의 미천한 지식이 더욱 문제를 어렵게 만들었네요. 제가 풀어본 방법은 3가지 입니다.

 

1. Collections.sort() 를 이용한 정렬 → 시간초과 발생
2. 힙 구현 및 정렬 → 로직이 꼬임, 시간초과
3. Java의 PriorityQueue이용 → 성공

 

처음엔 해시 카테고리인 문제임에도 불구하고 Collections.sort() 를 이용하였습니다. 역시나 '시간초과'가 발생하였습니다. 이렇게 처음 푼 이유는 물론 익숙한대로 쓰다보니 쓴 것도 있지만 Collections.sort() 도 시간복잡도가 O(Nlog(N))라고 생각하였고 다른 방법으로 풀어도 빨라봤자 정렬할 때 이 시간복잡도 보다는 빠르지 않을 것이라 생각하였습니다. 하지만 결과적으로 봤을 때 저의 이러한 가정은 반은 맞고 반은 틀렸습니다. 맞은 부분은 시간 복잡도가 O(Nlog(N)) 라는 점입니다¹. 그렇지만 나머지 반이 틀린 이유는 정렬만 생각하기엔 문제 풀기에 부족하다는 것입니다. 즉, 정렬 한번만 한다는 것이 아닙니다.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        List<Integer> scovilleList = Arrays.stream(scoville).boxed().collect(Collectors.toList());

        while(Collections.min(scovilleList) < K) {
            Collections.sort(scovilleList);
            int temp1 = scovilleList.remove(0);
            int temp2 = scovilleList.remove(0);
            int newScoville = temp1 + (temp2 * 2);
            scovilleList.add(newScoville);
            if(newScoville < K && scovilleList.size() == 1) return -1;
            answer++;
        }
        return answer;
    }
}

위는 처음에 제가 Collections.sort 로 풀었을 때 입니다. 매 반복문 마다 정렬을 해줘야합니다. 그런데 문제 조건에 scoville의 길이가 1 이상 1,000,000이라는 것과 K가 1,000,000,000이하라는 점을 생각하면 매번 이렇게 정렬해줘선 너무 비효율적입니다.

 

그렇기 때문에 heap이라는 개념이 필요합니다! heap은 처음 만들고 나서 가장 큰 값(Max heap)과 가장 작은 값(Min heap)을 가져오기에 정말 효율적으로 가져올 수 있습니다. heap이라는 질서 아래 있기 때문에 문제에서 요구하는 가장 작은 값을 바로바로 찾을 수 있으며 새로운 값을 넣더라도 heap질서아래 빠르게 해당 위치에 찾아가게 만들 수 있습니다.

출처 : https://java2blog.com/heap-sort-in-java/

 

이렇게 heap의 필요성을 느끼고 heap을 인터넷을 보면서 만들어보았습니다.²

    void heapify(List<Integer> list, int i, int size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min;
        if(left <= size && list.get(left) < list.get(i)) {
            min = left;
        } else {
            min = i;
        }

        if(right <= size && list.get(right) < list.get(min)) {
            min = right;
        }

        if(min != i) {
            swap(list, i, min);
            heapify(list, min, size);
        }
    }

    void makeHeap(List<Integer> list) {
        for (int i = (list.size() - 1) / 2; i >= 0; i--) {
            heapify(list, i, list.size() - 1);
        }
    }

    void swap(List<Integer> list, int index1, int index2) {
        int temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }

하지만.. 역시나 제가 만든 것은 치밀하지 않게 만들다보니 막상 문제에 적용하려고 보니 빈틈투성이더라구요. 그래서 어떻게 하나 고민을 하고 있었는데 다른 사람들은 자바의 PrioirtyQueue 를 쓰더라구요.

저는 PrioirtyQueue 의 존재에 대해선 들어봤는데 한번도 안써보다보니 뭔지 잘 몰랐습니다. 그런데 이게 제가 구현하려고 애쓰던 힙을 구현한것이더라구요. 기본이 루트가 가장 작은 값으로 구성되어 Min Heap으로 구성되어 있으며, 가장 좋은 점은 제가 값을 꺼내거나 다시 넣으면 알아서 heapify한다는 점입니다. 그렇다보니 위 문제를 정말 간단하게 해결할 수 있었습니다.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> queue = new PriorityQueue();
        for (int i : scoville) {
            queue.offer(i);
        }

        while(queue.peek() < K) {
            if(queue.size() == 1) return -1;
            int temp1 = queue.poll();
            int temp2 = queue.poll();
            int newFood = temp1 + (temp2 * 2);
            queue.offer(newFood);
            answer++;
        }
        return answer;
    }
}

뭔가 제가 문제를 푼게 아니라 이 PriorityQueue 가 다 풀어준 기분입니다.

 

만약 default인 Min heap이 아니라 Max heap으로 구현하고 싶다면 다음과 같이 PriorityQueue 를 선언하면 됩니다.

Queue<Integer> queue = new PriorityQueue(Collections.reverseOrder());

 

 

---

1 https://stackoverflow.com/questions/25492648/what-is-the-time-complexity-of-collectionssort-method-in-java↩

2 https://java2blog.com/heap-sort-in-java/↩