[JS] 징검다리 건너기

문제를 푸는 접근방식은 단순했다.

 

k범위만큼씩 자르면서 해당 범위의 최댓값중 가장 작은 값을 얻어내면 된다.

 

[ 2, 4, 5 ]

[ 4, 5, 3 ]

[ 5, 3, 2 ]

[ 3, 2, 1 ]

[ 2, 1, 4 ]

[ 1, 4, 2 ]

[ 4, 2, 5 ]

[ 2, 5, 1 ]

 

예제로 따지면 위 범위중에서 범위안의 최댓값 중 최솟값은 3이다. 따라서 정답이 3이 되게 된다!

 

하지만 아래와 같이 내장함수를 사용해서는 풀 수 없었다. (예상한대로) 

 

function solution(stones, k) {
    
    let ret = Infinity
    
    for (let i = 0 ; i <= stones.length-k ; i++){
        ret = Math.min(ret , Math.max(...stones.slice(i,i+k)))
    }
    return ret
}

 

 

따라서 최대 힙을 구현해서 사용해보았다. 그런데 왜 마지막 케이스에 시간초과가.. 아무래도 조금 다른 방법이 필요한 듯 싶다.

 

class maxHeap {
  constructor() {
    this.ary = [0];
  }

  swap(aIdx, bIdx) {
    const c = this.ary[aIdx];
    this.ary[aIdx] = this.ary[bIdx];
    this.ary[bIdx] = c;
  }

  push(value) {
    this.ary.push(value);
    let idx = this.ary.length - 1;
    let parentIdx = ~~(idx / 2);
    while (parentIdx > 0 && this.ary[idx][1] > this.ary[parentIdx][1]) {
      this.swap(idx, parentIdx);
      idx = parentIdx;
      parentIdx = ~~(idx / 2);
    }
    
  }
  pop() {
    if (this.ary.length === 1) return undefined;
    if (this.ary.length === 2) return this.ary.pop();
    const ret = this.ary[1];
    this.ary[1] = this.ary.pop();
    let idx = 1;

    while (idx < this.ary.length) {
      const leftIdx = idx * 2;
      const rightIdx = idx * 2 + 1;
      let mainIdx = leftIdx;
      if (leftIdx >= this.ary.length) break;
      if (
        rightIdx < this.ary.length &&
        this.ary[rightIdx][1] > this.ary[leftIdx][1]
      )
        mainIdx = rightIdx;

      if (this.ary[mainIdx][1] < this.ary[idx][1]) break;
      this.swap(idx, mainIdx);
      idx = mainIdx;
    }
    return ret;
  }
    
    getMax(){
        if (this.ary.length===1) return undefined
        return this.ary[1]
    }
}

function solution(stones, k) {
    
    const heap = new maxHeap()
    
    for(let i = 0 ; i < k ; i++){
        heap.push([i,stones[i]])
    }
    
    let ret = heap.getMax()[1]
    for (let i = k ; i < stones.length ; i++){
        heap.push([i,stones[i]])
        while(heap.getMax()[0] <= i-k) heap.pop()
        ret = Math.min(ret,heap.getMax()[1])
    }
    
    return ret
    
}

 

 

근데 조금 찾아보니 파이썬의 heapq라이브러리를 활용한 분은 나랑 같은 똑같은 방법으로 해결한 사람이 있다 ㅠㅠ..

아마 내가 heap을 조금 이상하게 구현해서 그렇지 않을까 싶다.. (조금억울)

 

 

 

 

조금 찾아보니 이분탐색을 이용하는 개념이 있길래 힌트를 얻어서 문제를 해결해보았다.

 

문제의 핵심은 배열이 20만개로 생각보다 적은 것과 안에 들어가는 수가 크다는 것이다.

 

즉 보통같으면 될수 있는 사람을 천천히 구해가는 문제로 풀겠지만 이 문제의 경우 이분탐색을 활용하여 1~20억 까지의 사람들 중에서 정답인 수를 고르는 문제로 바꿀 수 있는 문제였다.

 

function solution(stones, k) {
  let left = 0;
  let right = 2000000000;

  while (left <= right) {
    const mid = ~~((left + right) / 2);
    let isCanGo = true;
    let cnt = 0;
    for (let i = 0; i < stones.length; i++) {
      if (stones[i] - mid <= 0) cnt += 1;
      else cnt = 0;
      if (cnt === k) {
        isCanGo = false;
        break;
      }
    }
    if (isCanGo) left = mid + 1;
    else right = mid - 1;
  }

  return left;
}