99클럽 9일차 TIL (240730)

[Middler] 오늘의 문제 : 더 맵게

 

걸린시간 : 28분

권장시간 : 30분

 

오늘의 회고

heap 자료구조를 활용해서 풀어야하는 문제였다. 여기서 힙(heap)이란 '완전 이진 트리'의 일종으로 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조 입니다. 힙은 최대힙(Max-heap), 최소힙(Min-heap) 으로 구분하며 최대힙은 부모노드가 자식노드보다 크거나 같은 값을 가지는 구조이고, 최소힙은 부모노드가 자식노드보다 작거나 같은 특징을 같습니다. 

 

코딩테스트에서 최소힙은 우선순위 큐 자료구조를 구현하는 데 주로 사용됩니다. 이번 문제를 풀 때 최소힙을 이용하여 문제를 풀 수 있었습니다. 

 

문제 풀이

내 생각

1. 스코빌 지수 배열을 최소힙으로 구현한다.

2. 최소힙의 루트 노드가 K보다 크지 않을 때까지, 루트 노드와 그 다음 노드를 꺼내어 새로운 스코빌 지수를 계산한다.

  - 노드의 수가 2개 이하인 경우에는 모든 음식 스코빌 지수를 K 이상으로 만들 방법이 없기 떄문에 -1을 리턴한다.

3. 계산한 값의 노드를 넣어주고 횟수를 +1해준다.

 

1. python

import heapq
def solution(scoville, K):
    answer = 0
    
    # 최소힙을 생성해 넣어준다.
    heap = []
    for i in scoville :
        heapq.heappush(heap, i)
    
    # heap[0] 이 K보다 작다면 
    # 가장안매운 음식과 두번째로 안매운 음식을 찾아서 새로 heap에 넣는다.
    while heap[0] < K :
        # 음식의 개수가 1개일때, K보다 작다면 모든음식 스코빌 지수를  K이상으로 만들수 없으니까 -1을 리턴한다.
        if len(heap) < 2 :
            return -1
            
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        
        heapq.heappush(heap,first + (second*2))
        answer+=1
    
    return answer

 

2. javascript

- 자바스크립트는 힙 라이브러리가 없다. 직접 최소힙을 구현해야한다.

class MinHeap {
    constructor() {
        this.heap = [];
    }
    size() {
        return this.heap.length;
    }
    swap(idx1, idx2) {
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
    }
    add(value) {
        this.heap.push(value);
        this.bubbleUp();
    }
    bubbleUp(){
        let index = this.heap.length - 1;
        let parentIdx = Math.floor((index -1) / 2);
        
        while( this.heap[parentIdx] && this.heap[index] < this.heap[parentIdx]) {
            this.swap(index, parentIdx);
            index = parentIdx;
            parentIdx = Math.floor((index -1) / 2);
        }
    }
    poll(){
        if(this.heap.length === 1) {
            return this.heap.pop()
        }
        
        const value = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return value;
    }
    bubbleDown() {
        let index = 0;
        let leftIndex = index*2 + 1;
        let rightIndex = index*2 + 2;
        
        while( (this.heap[leftIndex] && this.heap[leftIndex] < this.heap[index]) 
              || this.heap[rightIndex] && this.heap[rightIndex] < this.heap[index]) {
            
            let smallerIdx = leftIndex;
            
            if( this.heap[rightIndex] && this.heap[rightIndex] < this.heap[smallerIdx]) {
                smallerIdx = rightIndex
            }
            
            this.swap(index, smallerIdx);
            index = smallerIdx
            leftIndex  = index * 2 + 1;
            rightIndex  = index * 2 + 2;
        }
    }
}

class PriorityQueue extends MinHeap {
    constructor() {
        super();
    }
    enqueue = (value) => this.add(value);
    dequeue = () => this.poll();
    length = () => this.size();
}

function solution(scoville, K) {
    var answer = 0;
    
    // 음식을 스코빌 지수 기준으로 우선순위 큐에 담는다.
    const q = new PriorityQueue();
    scoville.forEach(item=>q.enqueue(item))
    
    // 힙의 최상단 부모노드가 K보다 작은지 확인하며 반복한다.
    while( q.heap[0] < K ) {
        // 음식의 개수가 1개일 때 더이상 스코빌 지수를 K이상으로 만들 수 없으므로 -1을 리턴한다.
        if( q.length() < 2 ) {
            return -1
        }
        let first = q.dequeue();
        let second = q.dequeue();
        
        q.enqueue(first + (second*2));
        answer+=1;
    }
    
    return answer;
}

 

 

느낀 점

js에 비해 파이썬이 참편리하다. 하지만 js로 최소힙을 구현하는 코드는 외워서 나의 무기로 가지고가자

 

---

 

[Challenger] 최소 힙

걸린시간 : 30분

권장시간 : 1시간 30분

 

오늘의 회고

위의 미들러 문제와 같이 힙을 구현하는 문제이다. 파이썬은 heapq라이브러리를 사용하면 어렵지않게 풀수 있다는 장점이 있다. x를 입력받고 문제 조건대로 구현해주면 되었다.

 

다만, 백준에서 파이썬 입출력 방식에 대해서 모르고 있었어서 sys 라이브러리 혹은 input() 메서드에 대해 알 수 있는 좋은 기회였다.

 

문제 풀이

내 생각

1. 입력받을 때, x가 0이면 heap이 있을 때 pop하고 없을 때는 0을 리턴한다.

2. 0이 아닌 정수가 주어진다면 heap에 넣는다.

 

1. python

import sys
import heapq
def solution() :
    n = int(sys.stdin.readline().rstrip())
    heap = []
    
    for i in range(n) :
        x = int(sys.stdin.readline().rstrip())
        
        if x == 0 :
            if len(heap) > 0 :
                print(heapq.heappop(heap))
            else :
                print(0)
        else :
            heapq.heappush(heap, x)
    
solution()