[프로그래머스][Java][Lv.2] 더 맵게

 

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

프로그래머스

 

 

첫번째 틀린 풀이

 

실전 PS상황에서는 해당 문제가 어떤 유형인지 알려주지 않기 때문에, 일단 내 방식대로 접근했다.

하지만 2가지 문제점이 있었다.

(1) 시간 초과 : 반복분 조건포함해서 N² + 정렬 NlogN으로 -> N²logN이 되버림
(2) 제한 사항 누락 : 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1 반환하는 부분이 없음

 

테스트케이스로 틀린 예시는 아래와 같다.

입력:
scoville(int[]) : [1,2,3,9,10,12]
K(int) : 1000000

출력:
-1

 

import java.util.Arrays;
class Solution {  // O(N^2) * O(NlogN) == O(N^2logN)
    public int solution(int[] scoville, int K) {
        int answer = 0;

        // O(N²) => (Wheil 루프의 반복 횟수 x for 루프 내부 시간복잡도)
        // Wheil 루프의 반복 횟수는 최악의 경우 배열의 모든 원소가 K보다 작은 경우이기 때문에 
        // 배열 크기인 N에 비례한다.
        while (checkUnderK(scoville, K)) {
            Arrays.sort(scoville); // 퀵 소트 알고리즘 O(NlogN)
            int Most = scoville[0];
            int More = scoville[1];
            int mixed = Most + (More * 2);
            scoville[1] = mixed;
            scoville = Arrays.copyOfRange(scoville,1,scoville.length);
            answer++;
        }

        return answer;
    }
    public boolean checkUnderK(int[] scoville, int K) {
        for (int i = 0; i < scoville.length; i++) {
            if (scoville[i] < K) return true;
        }
        return false;
    }
}

 

 

두번째 정답 풀이

 

첫번째 풀이는 각 원소인 스코빌 지수를 모두 K이상으로 만들기 위해 반복문을 사용하고, 매 반복마다 배열을 정렬하고 첫 번째와 두 번째 워소를 조합하여 새로운 원소를 만들고 배열을 조정하는 작업을 수행한다.

이러한 방식은 배열을 정렬하고 조정하는과정이 반복될때 시간 복잡도가 높아져 시간초과가 발생한다.

 

그렇다면 문제를 봤을때 이걸 `힙`으로 접근해야 한다는 것을 어떻게 파악할 수 있을까?

스코빌 지수가 가장 작은 음식 2개를 효율적으로 찾아내는 것이 목적이므로 최소 힙을 떠올려야 한다

최소 힙은 가장 작은 원소가 항상 루트에 위치하도록 하는 자료구조입니다.

 

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        // 우선순위 큐를 사용하여 최소 힙 구현
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : scoville) {
            pq.offer(s);
        }

        while (pq.size() > 1 && pq.peek() < K) {
            int most = pq.poll();
            int more = pq.poll();
            int mixed = most + (more * 2);
            pq.offer(mixed);
            answer++;
        }

        // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
        if (pq.peek() < K) {
            return -1;
        }

        return answer;
    }
}

테스트 1 〉	통과 (0.47ms, 75.3MB)
테스트 2 〉	통과 (0.48ms, 79.6MB)
테스트 3 〉	통과 (0.48ms, 70MB)
테스트 4 〉	통과 (0.47ms, 80.6MB)
테스트 5 〉	통과 (0.31ms, 68.4MB)
테스트 6 〉	통과 (1.75ms, 70.9MB)
테스트 7 〉	통과 (2.75ms, 65.4MB)
테스트 8 〉	통과 (1.00ms, 75.3MB)
테스트 9 〉	통과 (0.74ms, 75MB)
테스트 10 〉	통과 (2.28ms, 77.5MB)
테스트 11 〉	통과 (3.08ms, 66.8MB)
테스트 12 〉	통과 (4.81ms, 84.3MB)
테스트 13 〉	통과 (2.43ms, 79.6MB)
테스트 14 〉	통과 (0.44ms, 73.2MB)
테스트 15 〉	통과 (2.56ms, 80.4MB)
테스트 16 〉	통과 (0.30ms, 78.9MB)
테스트 17 〉	통과 (0.30ms, 73MB)
테스트 18 〉	통과 (0.31ms, 83.8MB)
테스트 19 〉	통과 (0.45ms, 80.5MB)
테스트 20 〉	통과 (0.33ms, 78.7MB)
테스트 21 〉	통과 (0.32ms, 70.1MB)
테스트 22 〉	통과 (0.48ms, 71.7MB)
테스트 23 〉	통과 (0.42ms, 76.7MB)
테스트 24 〉	통과 (0.42ms, 76.7MB)
테스트 25 〉	통과 (0.40ms, 77.7MB)
테스트 26 〉	통과 (0.36ms, 72.3MB)

효율성 테스트

테스트 1 〉	통과 (148.23ms, 67.7MB)
테스트 2 〉	통과 (274.52ms, 86.6MB)
테스트 3 〉	통과 (1295.58ms, 122MB)
테스트 4 〉	통과 (251.60ms, 66.5MB)
테스트 5 〉	통과 (3245.08ms, 124MB)

 

 

힙(Heap)에 대한 설명

힙은 완전 이진 트리(Complete Binary Tree) 구조를 가지며, 부모 노드가 자식 노드보다 작은 값 또는 큰 값으로 정렬된 자료구조입니다.

 

• 최소 힙(Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같습니다.
• 최대 힙(Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같습니다.

힙을 사용하면 최솟값 또는 최댓값을 빠르게 찾을 수 있습니다. 즉, 가장 우선순위가 높은 요소를 빠르게 접근할 수 있습니다.

 

자바에서 힙을 구현할 수 있는 컬렉션은 PriorityQueue이다.

내부적으로 힙(Heap)을 사용하여 요소를 저장하고 우선순위에 따라 정렬된 상태를 유지한다.

PriorityQueue:

최소 힙(Min Heap): 기본적으로는 작은 값이 우선순위가 높게 설정되어 있습니다. 따라서 가장 작은 요소가 큐에서 먼저 나오게 됩니다.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

 

최대 힙(Max Heap): 최대 힙을 구현하려면 초기화 시에 Comparator를 역순으로 지정해야 합니다.

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

 

코드 예제

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // 최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(3);
        minHeap.offer(1);
        minHeap.offer(4);

        // 출력: 1, 3, 4
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }

        // 최대 힙
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(4);

        // 출력: 4, 3, 1
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

 

 

힙의 활용:

• 우선순위 큐: PriorityQueue를 사용하여 가장 높은 우선순위의 요소에 빠르게 접근할 수 있습니다.
• 힙 정렬: 힙 정렬 알고리즘에서 사용됩니다.
• 다익스트라 알고리즘: 최단 경로를 찾는 알고리즘 중 하나로, 우선순위 큐를 활용하여 구현됩니다.
• 힙은 효율적인 삽입, 삭제, 최소/최대 검색을 제공합니다.