[프로그래머스] 숫자 변환하기 JS

 

풀이방법!

bfs로 배열값을 갱신하면서 풀었습니다
x에서부터 3가지 방법으로 갈 수 있는 값들을 방문하면서
횟수가 적으면 table을 갱신하고 큐에 넣어주었습니다.

그런데 생각해보니 배열값을 최소값으로 갱신하는게 아니라 true,false로 방문 여부만 갱신해도 상관없는
전형적인 bfs 문제였습니다

그리고 이번 문제는 배열의 shift를 사용하는 경우 시간초과가 발생해서 직접 큐를 구현했습니다

예전에 백준에서
https://www.acmicpc.net/problem/13549

숨바꼭질 3 문제를 풀었는데

이 문제의 경우는 이동할 때 0초가 걸리는 경우가 있어서

최소값을 갱신하면서 풀었습니다

문제의 조건을 잘 생각하면서 풀어야겠네요

 

 

최소값 갱신

function solution(x, y, n) {
  //bfs

  //각 숫자에 도달하는 최소 연산 횟수를 저장할 테이블
  const table = new Array(y + 1).fill(Infinity);
  const q = new Queue();
  const calc = [
    ['+', n],
    ['*', 2],
    ['*', 3],
  ];

  q.enqueue({ val: x, cnt: 0 });
  table[x] = 0;

  //큐가 빌 때까지
  while (q.size) {
    const current = q.dequeue();

    //3번의 연산을 반복(+n, *2, *3)
    for (let i = 0; i < 3; i++) {
      const next = calcNextVal(current.val, calc[i][0], calc[i][1]);

      //연산 결과가 y이하이고 더 적은 횟수로 방문 가능하면 table 갱신하고 큐에 넣어줌
      if (next <= y && table[next] > current.cnt + 1) {
        table[next] = current.cnt + 1;
        q.enqueue({ val: next, cnt: current.cnt + 1 });
      }
    }
  }

  function calcNextVal(currentValue, operator, num) {
    if (operator === '+') return currentValue + num;
    return currentValue * num;
  }

  return table[y] !== Infinity ? table[y] : -1;
}

 

 

 

visited로 방문여부만 판단

function solution(x, y, n) {
  //bfs

  //각 숫자에 도달하는 최소 연산 횟수를 저장할 테이블
  const visited = new Array(y + 1).fill(false);
  const q = new Queue();
  const calc = [
    ['+', n],
    ['*', 2],
    ['*', 3],
  ];

  q.enqueue({ val: x, cnt: 0 });
  visited[x] = true;

  //큐가 빌 때까지
  while (q.size) {
    const current = q.dequeue();
      
      if(current.val === y){
          return current.cnt;
      }

    //3번의 연산을 반복(+n, *2, *3)
    for (let i = 0; i < 3; i++) {
      const next = calcNextVal(current.val, calc[i][0], calc[i][1]);

      //연산 결과가 y이하이고 방문 안했으면 큐에 넣어줌
      if (next <= y && !visited[next]) {
        visited[next] = true;
        q.enqueue({ val: next, cnt: current.cnt + 1 });
      }
    }
  }

  function calcNextVal(currentValue, operator, num) {
    if (operator === '+') return currentValue + num;
    return currentValue * num;
  }

  return -1;
}

 

 

 

큐 구현 코드

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(val) {
    const node = new Node(val);
    if (!this.front) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }

    return ++this.size;
  }

  dequeue() {
    if (!this.front) return null;

    const node = this.front;
    if (this.front === this.rear) {
      this.rear = null;
    }
    this.front = this.front.next;
    this.size--;

    return node.val;
  }
}