프로그래머스 - [더 맵게] 42626

문제 링크

코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 더 맵게

 

 

문제 설명

문제 자체는 어렵지 않다.

그저 int 배열 scoville 을 오름차순으로 정렬한 후에 가장 앞의 두 값으로 음식의 스코빌 지수를 구한다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

그리고 앞의 두 값은 지우고, 섞음 음식의 스코빌 지수를 다시 넣고 정렬한다.

scovile 배열의 크기의 범위는 2 ~ 10^6 ,

K값의 범위는 0 ~ 10^9 이다.

 

 

풀이

풀이는 아주 간단하게 배열을 정렬해주기만 한다면 된다. 그렇지만 어떻게 하느냐가 중요하다.

 

scovile 의 원소 갯수를 N 이라 했을 때 N의 최대값은 100만이다. 정렬을 잘못했다간 당연히도 시간초과가 날 것.

Arrays.sort(), Collections.sort() 함수가 대표적인데, 두 함수의 시간복잡도를 살펴보자.

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

 

시간 복잡도가 낮은 Collections.sort()로 scoville 배열을 int 리스트로 바꾼 후, 정렬을 수행했다.

 

그런데 여기서 치명적인 결함이 발생한다.

 

문제의 설명을 보면, 우리는 음식을 계속해서 섞어야 될수도 있다.

정렬을 한번 하고 마는 것이 아니라  배열의 모든 값이 전부 K 이상일 때까지 섞는것이다. 섞는 행위 1번당 정렬도 1번씩 수행해줘야 한다.  N개의 원소가 있다면, 최악의 경우 (N-1) 번까지 반복할 수 있다.

따라서 최악의 경우 시간복잡도는 O(N*(N*logN)) 이 되어버린다.

 

따라서 더 빠른 정렬 방법이 필요한데, 우선순위 큐를 사용하면 된다.

 

 

우선순위 큐

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

힙은 특정한 규칙을 가지는 트리로, 힙을 이용해 우선순위큐를 구현할 수 있다.

 

힙 구조를 생성하는 데에는 O(logN)의 시간이 든다.

여기서 힙구조를 생성한다는 뜻은 최대 힙 혹은 최소 힙 구조를 만든다는 뜻으로, 정렬된 완전 이진트리 상태를 만드는 것을 의미한다.

따라서 정렬에 드는 시간이 O(logN) 이므로 N번 정렬을 반복해도 O(N*logN)의 시간복잡도를 가진다.

 

 

소스코드

public int solution(int[] scoville, int K) {
    int answer = 0;
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int i : scoville) {
        heap.offer(i);
    }
    if(heap.peek()>=K) return 0;

    while(heap.peek()<=K && heap.size() >= 2){
        int a = heap.peek();  heap.poll();
        int b = 2 * heap.peek();  heap.poll();
        heap.offer(a + b);
        answer++;
    }
    if(heap.peek() < K) return -1;
    return answer;
}

 

 

키 포인트

정렬 알고리즘은 시간복잡도를 고려해야 한다. 가장 분명하게 그 성능차이가 드러나며, 그 차이가 심각한 다운을 발생시킬수도 있을것이다. 힙 정렬은 아주 중요한 알고리즘으로, 이진트리를 만든 후에 최대 힙 혹은 최소 힙을 생성하기 위해 O(logN), 즉 트리의 높이만큼 내려가며 모든 원소들을 정렬하는 데에는 O(N*logN)이 걸리게 된다.