🌶️

더 맵게

레벨

LV.2

날짜

Sep 27, 2023

링크

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

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

강의에서 배운 MinHeap 사용

코드

정은

구현

배열 구조의 힙 클래스를 생성

최소 힙으로 삽입, 삭제 구현 (+ 최소값 가져오기, 사이즈 가져오기)

삽입

배열 맨 끝에 push
부모와 비교하여 swap

삭제

최소값 ,즉 인덱스 1 값을 삭제 후 반환
마지막 인덱스를 새로운 인덱스 1 값으로
자식과 비교해서 swap

코드 실행

힙에 배열 값들을 넣어줌
최소 값이 K 이상일 때까지 힙 삭제 연산 후에 삽입 연산 실행

코드

종혁

구현

minHeap을 사용해서 제일 앞 요소, 그 다음 요소를 pop하여 계산하고, 계산해서 나온 값을 push하여 힙 정렬을 깨트리지 않고 원하는 위치에 넣음

heap의 root요소가 K보다 크다면 , 전체 요소가 K보다 큰 값이기 때문에 count를 리턴하고, 크지 않다면 -1 리턴

코드

재웅

구현

강의시간에 작성한 MaxHeap을 변환하여 사용하였음

가장 작은 두 원소(Left, Right)를 추출, 스코빌 계산하여 다시 추가

최소 원소가 K를 넘어설때까지 (2) 반복

테스트케이스 및 효율성 실패

코드

해설

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

힙을 전부 구현해서 시간이 걸렸다!

예외처리 추가하기

👧🏻

정은

파이썬으로 하다가 자스로 힙을 모두 구현하려니 빡셌다

덕분에 힙 개념은 확실히 안 까먹을 것 같다!

👦🏻

종혁

구현과정에서 헷갈려서 검색을 이용함

예외케이스를 찾는게 좀 힘들었던것같다

👦🏻

재웅


class MinHeap {
  constructor() {
      this.heap = [null];
  }

  push(value) {
      this.heap.push(value);
      let currentIndex = this.size();
      let parentIndex = Math.floor(currentIndex / 2);

      while(parentIndex !== 0 && this.heap[parentIndex] > value) {
        const temp = this.heap[parentIndex];
        this.heap[parentIndex] = value;
        this.heap[currentIndex] = temp;

        currentIndex = parentIndex;
        parentIndex = Math.floor(currentIndex / 2);
      }
  }

  pop() {
      const returnValue = this.heap[1];
      this.heap[1] = this.heap.pop();

      let currentIndex = 1;
      let leftIndex = 2;
      let rightIndex = 3;
      while(
        this.heap[currentIndex] > this.heap[leftIndex] ||
        this.heap[currentIndex] > this.heap[rightIndex]
        ) {
        if(this.heap[currentIndex] > this.heap[leftIndex]) {
          const temp = this.heap[currentIndex];
          this.heap[currentIndex] = this.heap[leftIndex];
          this.heap[leftIndex] = temp;
          currentIndex = leftIndex;
        } else {
          const temp = this.heap[currentIndex];
          this.heap[currentIndex] = this.heap[rightIndex];
          this.heap[rightIndex] = temp;
          currentIndex = rightIndex;
        }
        leftIndex = currentIndex * 2;
        rightIndex = currentIndex * 2 + 1;
      }
      return returnValue;
  }
  size() {
      return this.heap.length - 1;
  }
}

function solution(scoville, k) {
    let count = 0;
    // 최소힙
    const heap = new MinHeap();
    scoville.forEach(value => heap.push(value));
    while(heap.heap[1] < k && heap.size() > 1) {
        const firstMin = heap.pop();
        const secondMin = heap.pop();
        const newValue = firstMin + (secondMin * 2);
        heap.push(newValue);
        count++;
    }
    return heap.heap[1] >= k ? count : -1;
}


class MinHeap {
    constructor (){
        this.heap = [null];
    }
    
    getMin() {
        return this.heap[1];
    }
    
    size() {
        return this.heap.length-1;
    }
    
    insert(value) {
        this.heap.push(value);
        
        if(this.size() <= 1) {
            return;
        }
        
        let currentIdx = this.size();
        let parentIdx = Math.floor(currentIdx/2);
        
        while(currentIdx > 1 && this.heap[currentIdx] < this.heap[parentIdx]) {
            [this.heap[currentIdx], this.heap[parentIdx]] = [this.heap[parentIdx],this.heap[currentIdx]];
            
            [currentIdx,parentIdx] = [parentIdx,Math.floor(currentIdx/2)];
        }
    }
    
    remove() {
        const smallestValue = this.getMin();
        
        if (this.size() < 1) {
            return null;
        } else if(this.size() === 1) {
            this.heap.pop();
        } else {
            this.heap[1] = this.heap.pop();
            
            let currentIdx = 1;
            let leftIdx = currentIdx*2;
            let rightIdx = leftIdx+1;
            
            while (this.heap[leftIdx] && this.heap[rightIdx] && (this.heap[currentIdx] > this.heap[leftIdx] || this.heap[currentIdx] > this.heap[rightIdx])) {
                if (this.heap[leftIdx] > this.heap[rightIdx]) {
                    [this.heap[currentIdx], this.heap[rightIdx]] = [this.heap[rightIdx], this.heap[currentIdx]];
                    currentIdx = rightIdx;
                } else {
                    [this.heap[currentIdx], this.heap[leftIdx]] = [this.heap[leftIdx], this.heap[currentIdx]];
                    
                    currentIdx = leftIdx;
                }
                
            leftIdx = currentIdx*2;
            rightIdx = leftIdx+1;                      
            }
        }
        
        return smallestValue;
    }
}

function solution(scoville, K) {
    var answer = 0;

    const heap = scoville.reduce((heap,value)=> {
        heap.insert(value);
        return heap;
    }, new MinHeap());
    
    while (heap.getMin() < K) {
        if(heap.size() <= 1) {
            return -1;
        }
        heap.insert(heap.remove()+heap.remove()*2);
        answer++;
    }
    
    return answer;
}


class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }
        push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }
  pop() {//root를 제거하고 제일 뒤 원소를 root로 
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0
    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;
      
			if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }
    return minValue;
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();

  for (const s of scoville) {
    minHeap.push(s);
  }

  let mixedCount = 0;

  while (minHeap.size() >= 2 && minHeap.heap[0] < K) {
		//힙에서 제일 앞,그 다음 요소를 pop한 후 계산한 다음, 그 값을 힙 정렬을 깨트리지 않고 다시 push
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixedScov = first + second * 2;
    minHeap.push(mixedScov);
    mixedCount++;
			//start : [1, 2, 3, 9, 10, 12]
      //[ 3, 5, 10, 12, 9 ]
      //[ 9, 12, 10, 13 ] 
  }

  return minHeap.heap[0] >= K ? mixedCount : -1;
-> 제일 앞 요소가 K 이상이라는 의미는 모든 값이 K이상이 됨 - count 리턴
}


class MinHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    // 1. 배열 맨 끝 노드에 값을 추가
    this.heap.push(value);

    // 2. 추가한 배열의 인덱스와 부모 노드 인덱스 추출
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    // 3. 부모 노드 우선순위가 더 높을 때까지 추가된 노드를 올림 (부모와 교환)
    while (parentIndex !== 0 && this.heap[parentIndex] > value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    // 1. 루트 요소 반환을 위해 임시로 상수에 저장
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    // 2. 노드 인덱스 초기 설정
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;

    // 3. 하위 노드들의 우선순위가 더 낮을 경우 반복문 종료
    while (this.heap[currentIndex] > this.heap[leftIndex] || this.heap[currentIndex] > this.heap[rightIndex]) {
      // 4. 자식 노드 우선순위를 비교, 더 낮은 것과 현재 노드를 바꿔줌
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    return returnValue;
  }

  peek() {
    return this.heap[1];
  }

  size() {
    return this.heap.length-1;
  }
}

function solution(scoville, K) {
    let answer = 0;
    const heap = new MinHeap();
    scoville.forEach((el) => heap.push(el));

    while (heap.peek() < K && heap.size() > 2) {
        const left = heap.pop();
        const right = heap.pop();
        const newItem = left + right * 2;
        heap.push(newItem);
        answer++;
    }

    return heap.peek() >= K ? answer : -1;
}


class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

    // 값을 넣되, 오름차 순 정렬함
  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;

    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

    // 값을 빼되, 오름차 순 정렬 함
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;

    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;

      if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }

    return minValue;
  }

  peek() {
    return this.heap[0];
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();

  for (const sco of scoville) {
    minHeap.push(sco);
  }

  let mixedCount = 0;

  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixedScov = first + second * 2;
    minHeap.push(mixedScov);
    mixedCount++;
  }

  return minHeap.peek() >= K ? mixedCount : -1;
}