[JS] 숫자 변환하기

문제 자체는 BFS를 활용해서 풀면 되겠다고 딱 생각이 들었다.

 

 

그런데 이 문제도 케이스의 범위가 커서 시간초과가 나왔다.

function solution(x, y, n) {
    let que = [[x,0]]
    
    while (que.length) {
        const [num,cnt] = que.shift()
        if (num===y) return cnt
        const calc = [num+n,num*2,num*3]
        
        for (const el of calc){
            if (el < y ) {
                que.push([el,cnt+1])
            }
            if (el === y) return cnt+1
        }
    }
    return -1
}

 

 

 

따라서 한번 나온 숫자는 추가적으로 확인할 필요가 없으니, 이를 기록해가면서 하면 시간초과가 나오지 않을 것이라 예상하고 수정했는데 이전 보단 케이스들을 많이 통과했지만 여전히 시간초과에 2케이스 정도 걸렸다.

function solution(x, y, n) {
    let que = [[x,0]]
    const dp = {}
    while (que.length) {
        const [num,cnt] = que.shift()
        if (num===y) return cnt
        const calc = [num+n,num*2,num*3]
        
        for (const el of calc){
            if (el < y && !dp[el]) {
                que.push([el,cnt+1])
                dp[el] = true
            }
            if (el === y) return cnt+1
        }
    }
    return -1
}

 

 

Queue를 연결리스트를 활용해서 구현해 본 이후, BFS를 했더니 통과하였다.

 

 

function Node(value) {
  this.value = value;
  this.next = null;
}

function Queue() {
  this.front = null;
  this.back = null;
  this.size = 0;

  this.enqueue = function (value) {
    const node = new Node(value);
    if (this.size === 0) {
      this.front = node;
      this.back = node;
    } else {
      this.back.next = node;
      this.back = node;
    }
    this.size++;
  };

  this.dequeue = function () {
    if (this.size === 0) {
      throw new Error("큐가 비었소");
    }
    const value = this.front.value;
    this.front = this.front.next;
    this.size--;
    if (this.size === 0) this.back = null;
    return value;
  };

  this.isEmpty = function () {
    return this.size === 0;
  };

  this.peek = function () {
    if (this.size === 0) return null;
    return this.front.value;
  };
}

function solution(x, y, n) {
    const que = new Queue()
    que.enqueue([x,0])
    
    const dp = {}
    while (que.size) {
        const [num,cnt] = que.dequeue()
        if (num===y) return cnt
        const calc = [num+n,num*2,num*3]
        
        for (const el of calc){
            if (el < y && !dp[el]) {
                que.enqueue([el,cnt+1])
                dp[el] = true
            }
            if (el === y) return cnt+1
        }
    }
    return -1
}

 

 

자바스크립트에 큐 자료구조가 라이브러리 형태라도 지원해주면 좋을텐데..

 

 

 

라고 생각한 순간 다른분들의 정답 코드를 보다가 굉장히 기발한 생각을 보았다. 결국, Queue가 앞에서부터 값을 하나씩 사용하는건데, 위 문제의 경우 무조건 Que의 값을 한번에 하나씩 빼서 사용한다.

 

이런경우, 배열에 단순히 push만 하면서 사용할 수 있었다.

 

 

const newData = [];
    for (const d of data) {
     ... push 로직
    }

 

위 방식처럼 Que 자료구조를 구현 안하고도 유사하게 사용할 수 있는 방법이 있었다.