프로그래머스 - 더 맵게

 

<문제>

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

프로그래머스

 

 

<문제 핵심>

1. 힙 자료구조

✅완전 이진 트리의 일종

✅기본 베이스는 배열 자료구조를 사용한다.

✅여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
✅힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
     간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

✅시간복잡도는 O(log n)을 가진다.

 

<힙에서의 부모 노드와 자식 노드의 관계>

✅ 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
✅ 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
✅ 부모의 인덱스 = (자식의 인덱스) / 2 -> ex. 5/2 를 해도 내림차순 적용해서 2로 연산 됌

<힙(heap)의 종류>

✅ 최대 힙(max heap)
개념: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

✅ 최소 힙(min heap)
개념: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

<문제 풀이과정 및 순서도>

풀이과정을 설명하기 전 처음으로 '힙' 자료구조를 풀어봤는데 자바스크립트는 heap 구조를 수작업으로 구현해야 하는 것을 알았다. 결국 문제를 풀지 못했고 구글링을 통해 문제 해설을 보며 경악을 금치 못한 것 같다.. 그래서 코드 한줄한줄 이해하느라 시간을 많이 할애했고 결론적으로 이해는 완료했다..

 

1. <힙 자료구조 설명>

✅ 클래스를 통해 최소 힙 으로 구현하고 heap 배열을 처음에 null로 초기화 한다.

-> 인덱스를 1 부터 사용하기 위해서 이다.

 

✅ push(): 새로운 값을 힙의 끝에 추가한 후 부모노드와 자식노드를 비교하는데 반복문이 끝나는 시점은 부모노드가 자식노드보다 작거나 같을 때 종료된다.(즉 부모노드가 자식노드 보다 큰 경우에는 계속 위치 조정을 해줘야함)

 

✅ pop(): heap 배열에서 0 인덱스는 사용하지 않으므로 1 인덱스가 루트 노드이다.

• 루트 노드를 제거한 후, 힙의 마지막 요소를 루트 노드로 이동시킨다.
• currentIdx는 현재 노드의 인덱스, leftIdx와 rightIdx는 각각 왼쪽 자식과 오른쪽 자식의 인덱스.
• 자식 노드 중 더 작은 값과 현재 노드를 교환하고, 인덱스를 업데이트하여 자식 노드로 이동한다. 이 과정을 자식 노드들이 현재 노드보다 크거나 같을 때까지 반복한다.

✅ isScoville() : 힙의 루트 노드가 힙에서 가장 작은 값을 가지고 있으므로 value보다 크거나 같은지를 판단하여 크거나 같다면 false를 리턴한다. 

 

<힙 자료구조 코드>

 

class MinHeap {
	constructor() {
		this.heap = [null];
	}
    
    push(value){
        this.heap.push(value);
        let currentIdx = this.heap.length - 1;
        let parentIdx = Math.floor(currentIdx / 2);
        
        while(parentIdx !== 0 && this.heap[parentIdx] > value){
            const temp = this.heap[parentIdx];
            this.heap[parentIdx] = value;
            this.heap[currentIdx] = temp;
            currentIdx = parentIdx;
            parentIdx = Math.floor(currentIdx/2);
        }
    }
    
    pop(){
      
      	// null과 원소 1개가 남았을 경우 나오지 않는 것을 대비
        if(this.heap.length === 2){
            return this.heap.pop();
        }
      
        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currentIdx = 1;
        let leftIdx = 2;
        let rightIdx = 3;
        

        
        while(
            this.heap[currentIdx] > this.heap[leftIdx]  ||
            this.heap[currentIdx] > this.heap[rightIdx]
        ){
            if(this.heap[leftIdx] > this.heap[rightIdx]){
                const temp = this.heap[currentIdx];
                this.heap[currentIdx] = this.heap[rightIdx];
                this.heap[rightIdx] = temp;
                currentIdx = rightIdx;
            }else{
                const temp = this.heap[currentIdx];
                this.heap[currentIdx] = this.heap[leftIdx];
                this.heap[leftIdx] = temp;
                currentIdx = leftIdx;
            }
            
            leftIdx = currentIdx * 2;
            rightIdx = currentIdx * 2 + 1
        }
        
        return returnValue;
    }
    
  // 스코빌 지수가 value보다 커지면 false
    isScoville(value){
        return this.heap[1] >= value;
    }
}

 

 

2. 구현한 힙 자료구조를 이용해 스코빌 지수를 k 이상으로 만들기 위한 섞는 횟수 구하기

 

✅ 섞는 횟수를 알아내기 위해 count 변수 0으로 초기화

✅ 입력받은 scoville 배열의 모든 요소들을 heap에 push한다.

✅ heap.isScoville(K)가 false인 동안 반복하고 즉 이 말은 최소 힙의 루트 노드가 k보다 작을 때 까지 반복한다.

✅ 문제 조건에 의거하여 새로운 스코빌 지수를 구하고( mixScoville = firstLowSpicy + (secondLowSpicy * 2) ) count를 증가시켜준다. -> pop()을 연속으로 호출하여 가장 작은 스코빌 지수, 두번째로 작은 스코빌 지수를 가져온다.

✅ 힙의 루트 노드를 pop하여 확인한다. 이 값이 K보다 작으면 더 이상 스코빌 지수를 높일 수 없으므로 -1을 반환한다. 반대라면 연산 횟수 count를 반환한다.

 

function solution(scoville, K) {
    const heap = new MinHeap();
    let count = 0;
    
  // heap에 push
    scoville.forEach((el)=>{
        heap.push(el);
    });
    
    const length = heap.heap.length;
    
  // 만약 heap안에 스코빌 지수가 다 아직 k보다 작다면 반복문 실행
    while(!heap.isScoville(K)){
      	// 배열의 길이보다 계산이 길어지는 것을 방지
        if(count >= length-1) break;
      
      	// 스코빌 지수 계산
        const firstLowSpicy = heap.pop();
        const secondLowSpicy = heap.pop();
        const mixScoville = firstLowSpicy + (secondLowSpicy * 2);
      // 넣어주기
        heap.push(mixScoville);
        count++;
    }
    
  // 스코빌 지수가 더 이상 커지지 않으면 -1을 return
    if(heap.pop()<K){
        return -1;
    }
    
    return count;
    
}

 

 

<전체 코드>

class MinHeap {
	constructor() {
		this.heap = [null];
	}
    
    push(value){
        this.heap.push(value);
        let currentIdx = this.heap.length - 1;
        let parentIdx = Math.floor(currentIdx / 2);
        
        while(parentIdx !== 0 && this.heap[parentIdx] > value){
            const temp = this.heap[parentIdx];
            this.heap[parentIdx] = value;
            this.heap[currentIdx] = temp;
            currentIdx = parentIdx;
            parentIdx = Math.floor(currentIdx/2);
        }
    }
    
    pop(){
      
      	// null과 원소 1개가 남았을 경우 나오지 않는 것을 대비
        if(this.heap.length === 2){
            return this.heap.pop();
        }
      
        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        
        let currentIdx = 1;//부모노드의 인덱스
        let leftIdx = 2;
        let rightIdx = 3;
        
        while(
            this.heap[currentIdx] > this.heap[leftIdx]  ||
            this.heap[currentIdx] > this.heap[rightIdx]
        ){
            if(this.heap[leftIdx] > this.heap[rightIdx]){
                const temp = this.heap[currentIdx];
                this.heap[currentIdx] = this.heap[rightIdx];
                this.heap[rightIdx] = temp;
                currentIdx = rightIdx;
            }else{
                const temp = this.heap[currentIdx];
                this.heap[currentIdx] = this.heap[leftIdx];
                this.heap[leftIdx] = temp;
                currentIdx = leftIdx;
            }
            
            leftIdx = currentIdx * 2;
            rightIdx = currentIdx * 2 + 1
        }
        
        return returnValue;
    }
    
  // 스코빌 지수가 value보다 커지면 false
    isScoville(value){
        return this.heap[1] >= value;
    }
}

function solution(scoville, K) {
    const heap = new MinHeap();
    let count = 0;
    
  // heap에 push
    scoville.forEach((el)=>{
        heap.push(el);
    });
    
    const length = heap.heap.length;
    
  // 만약 heap안에 스코빌 지수가 요소가 존재하면 반복
    while(!heap.isScoville(K)){
      	// 배열의 길이보다 계산이 길어지는 것을 방지
        if(count >= length-1) break;
      
      	// 스코빌 지수 계산
        const firstLowSpicy = heap.pop();
        const secondLowSpicy = heap.pop();
        const mixScoville = firstLowSpicy + (secondLowSpicy * 2);
      // 넣어주기
        heap.push(mixScoville);
        count++;
    }
    
  // 스코빌 지수가 더 이상 커지지 않으면 -1을 return
    if(heap.pop()<K){
        return -1;
    }
    
    return count;
    
}