[코테연습] 더맵게

오늘의 문제는 '힙(heap)' 관련 문제 였다.

 

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

프로그래머스

 

힙이라는게 뭘까?

 

우리의 Chat GPT 의 설명은 다음과 같다

 

-----

 

Heap은 컴퓨터 과학에서 중요한 자료 구조 중 하나로, 주로 우선순위 큐(priority queue)를 구현하는 데 사용됩니다. Heap은 다음 두 가지 형태로 나뉩니다:

1. 최대 힙(Max Heap): 부모 노드가 자식 노드들보다 크거나 같은 값을 가지는 이진 트리입니다. 따라서 최대 힙에서 루트 노드는 항상 가장 큰 값을 가집니다.
2. 최소 힙(Min Heap): 부모 노드가 자식 노드들보다 작거나 같은 값을 가지는 이진 트리입니다. 따라서 최소 힙에서 루트 노드는 항상 가장 작은 값을 가집니다.

Heap의 주요 특징은 다음과 같습니다:

• 완전 이진 트리(Complete Binary Tree): 힙은 완전 이진 트리의 형태를 가집니다. 즉, 트리는 왼쪽부터 차례로 채워지며, 마지막 레벨을 제외한 모든 레벨이 가득 차 있어야 합니다.
• 힙 속성(Heap Property): 최대 힙에서는 각 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 각 부모 노드가 자식 노드보다 작거나 같습니다.

Heap의 주요 연산은 다음과 같습니다:

• 삽입(Insertion): 새로운 요소를 힙에 추가합니다. 이 과정에서 힙 속성을 유지하기 위해 새로운 요소를 트리의 마지막 위치에 추가한 후, 부모 노드와 비교하며 적절한 위치로 이동시킵니다.
• 삭제(Deletion): 주로 루트 노드를 삭제합니다. 루트 노드를 삭제한 후, 마지막 요소를 루트 위치로 옮기고, 자식 노드들과 비교하며 적절한 위치로 이동시켜 힙 속성을 유지합니다.
• 최대값/최소값 찾기: 최대 힙에서는 루트 노드가 최대값이며, 최소 힙에서는 루트 노드가 최소값입니다.

힙은 다양한 알고리즘과 문제 해결에 활용됩니다. 예를 들어:

• 우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 이를 통해 높은 우선순위를 가진 작업을 효율적으로 처리할 수 있습니다.
• 힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, 평균 및 최악의 경우 시간 복잡도가 O(n log n)입니다.
• 다익스트라 알고리즘(Dijkstra's Algorithm): 최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 구현할 수 있습니다.

힙은 높은 성능과 효율성을 제공하기 때문에 다양한 응용 프로그램에서 널리 사용됩니다.

 

----

완벽하게 이해하지는 못했지만 그나마 이해할 수 있는 키워드는

'자료구조', '우선순위 큐', '이진트리', '다익스트라 알고리즘' 등이다. 

 

프로그래머스의 Heap 에 대한 문제 규정은 다음과 같다.

 

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

많은 언어에서 이미 구현된 우선순위 큐 라이브러리를 제공합니다. 이를 활용하면 효율적으로 문제를 풀 수 있습니다. 우선순위 큐를 이용해서 해결하기에 적합한 문제들을 만나보세요.

 

----

 

해당 문제를 풀기 위해서는 즉 언어마다 미리 제공해주는 '우선 순위 큐' 라이브러리를 사용하여 해결해야한다.

 

나는 Java 가 만들어 놓은 PriorityQueue 를 사용하여 문제를 해결했다.

 

해당 문제의 주요 포인트는 [  모든 음식의 스코빌 지수를 K 이상 ] 이상 만드는 것이다.

 

특정 자료구조에서 

가장 첫번째 인덱스를 자료구조에 Input 했을 때,   

첫번째 인덱스의 data 가 '가장 낮은 스코빌 지수' 라는 조건을 만족한다면,

해당 문제는 쉽게 풀릴 것이다.

 

이 경우 Queue 의 FILO 규칙 이나, Stack 의 FIFO 규칙으로는 자료구조의 형태를 불만족하기 때문에, '우선순위 큐'라는 개념이 필요하다.

 

Java 의 PriorityQueue 는 정의한 Sort 조건에 따라서 poll() 이나 offer() / add() 했을 때, sorting 한 조건에 따라서 리스트 자료구조를 가지게 된다.

 

즉, 

PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> o1-o2);

 

이라고 선언한다면 pQueue 는 오름차순으로 항상 data 를 정렬하며 poll() 했을 때, 가장 낮은 데이터를 출력하며, offer() / add() 했을 때 가장 낮은 데이터를  맨 앞으로 입력하게 된다.

 

해당 특성을 이용하여 문제를 풀면 다음과 같다.

 

public int solution(int[] scoville, int K) {

        int answer = 0;

        PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> o1-o2);

        for (int i = 0; i < scoville.length; i++) {

            int s = scoville[i];

            pQueue.offer(s);

        }

       

        while (pQueue.peek() < K) {

            if (pQueue.size() < 2) break;

           

            int _fir = pQueue.poll();

            int _sec = pQueue.poll();

            int _new = _fir + ( _sec * 2);

            pQueue.offer(_new);

            answer++;

        }

       

        if (pQueue.isEmpty() || pQueue.peek() < K) {

            answer = -1;

        }

        System.out.println("answer : "+answer);

        return answer;

    }

 

 

1. PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> o1-o2);

를 선언하여, 오름차순으로 데이터를 정렬할 수 있는 '우선순위 큐' 를 만든다.

2. scoville 리스트의 값을 pQueue 변수에 입력한다.

3. pQueue 의 data 값이 2개 미만 이거나, 첫번째 data 가 K 보다 더 클때까지 조건을 만족하는 while 반복문을 만든다.

4. 문제 요건에 따라, 첫번째 data 와 두번째 data 를 poll() 한뒤 다시 pQueue 에 first + (second * 2) 를 입력한다.

5. 최종 결과가 pQueue 의 첫번째 data 가 K 보다 작다면 answer 에 -1 를 입력하여 제출한다.

 

해당 문제는 우선순위 큐라는 자료구조의 존재 여부를 알려주는 좋은 문제라고 생각한다.