[골드 5] 14395번 4연산 ⭐️

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

예제

입력 	출력
7 392	+*+

풀이

dfs로 풀고자 했다.

1. s와 t가 같을 경우 0 출력
2. 스택에 있는 값(n)이 t와 일치하는 경우 : answer에 연산횟수를 넣어준다.
3. 스택에 있는 값(n)이 t와 일치하지 않는 경우 : n에 4연산을 한 값들을 스택에 [연산값, '연산횟수'] 형식으로 넣어준다.
   ex. [[15, '*+'], [40, '+-+'], [58, '++*-']]
4. 연산횟수가 가장 적은 것을 뽑아야 하므로 스택을 내림차순으로 정렬해준다.
   (pop할 때 연산횟수 적은 것 먼저 계산하기 위함)
5. 연산횟수 출력

• 가능한 연산이 없는 경우 : -1을 출력
• 가능한 연산이 있는 경우 :
  • 답이 1개만 있는 경우 : 해당 값을 출력
  • 답이 여러개 있는 경우 : 길이를 오름차순으로 정렬해 가장 짧은 연산이 여러개 있는지 체크
    • 짧은 연산이 1개만 있는 경우 : 해당 값을 출력
    • 짧은 연산이 여러개 있는 경우 : 사전 순으로 앞서는 값을 출력

첫 시도 : pop으로 했을 때는 answer에 값이 전부 안담겼다.
두 번째 시도 : shift로 했을 때는 테스트케이스는 맞았지만 정답은 틀렸다.
세 번째 시도 : 연산 길이가 작은 것을 항상 먼저 체크하도록 + pop으로 해서 맞았다.(시간은 좀 오래 걸렸지만)

const input = require('fs').readFileSync('ex.txt').toString().trim().split(' ');

const [s, t] = input.map(Number);

if (s === t) {
  console.log(0);
} else {
  let stack = [];
  stack.push([s, '']);
  let visited = {};
  let answer = [];

  while (stack.length) {
    let [n, calc] = stack.pop();

    if (!visited[n]) {
      visited[n] = true;
      if (n === t) {
        answer.push(calc);
      } else {
        stack.push([n + n, calc + '+']);
        stack.push([n * n, calc + '*']);
        stack.push([n - n, calc + '-']);
        stack.push([n / n, calc + '/']);
      }
    }
    stack.sort((a, b) => b[1].length - a[1].length); // 연산횟수 적은 것부터 탐색하기 위함
  }

  if (answer.length === 0) {
    console.log(-1);
  } else if (answer.length === 1) {
    console.log(answer.join(''));
  } else {
    let list = answer.sort((a, b) => a.length - b.length); // 길이 오름차순 정렬
    let min_list = list.filter((el) => el.length === list[0].length); // 길이 같은거 여러개인지 체크
    if (min_list.length === 1) {
      console.log(min_list.join(''));
    } else {
      console.log(min_list.sort()[0]); // 사전순 정렬
    }
  }
}