[프로그래머스/Swift] 154538번 - 숫자 변환하기

🔗 문제 링크

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

💡 구현 아이디어

1. y→x 로 역으로 구현 (y-n, y/2. y/3) : 풀고나니 x→y도 상관은 없는거 같다
2. [num-n], [num/2], [num/3]으로 구분 (num은 현재 숫자 - 디큐) num이 x 이하로 떨어지면 확인 안함
3. 이전에 구한 값이 없으면 횟수+1을 바로 저장, 이전에 구한 값이 있으면 횟수+1이 더 작으면 업데이트를 진행(인큐)
4. 큐가 빌때까지 진행하며 결과값에 [x]를 출력 이때 값이 없으면 -1

💻 코드

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
  var queue: [(Int, Int)] = [(y, 0)] // $0: 숫자, $1: 횟수
  var lenStore: [Int:Int] = [:] // key: 숫자, value: 최소 걸린 횟수 - queue와는 다름
  var idx: Int = 0
  var num: Int = 0
  var len: Int = 0
  let MAX: Int = 1000002
  while idx < queue.count {
    num = queue[idx].0 // 현재 숫자
    len = queue[idx].1 // 현재 숫자를 만든 숫자
    idx += 1
    
    if num-n >= x {
      let temp = lenStore[num-n, default: MAX]
      if len+1 < temp { // 횟수가 더 작을때만 업데이트 하고 큐에넣음
        lenStore[num-n] = len+1
        queue.append((num-n, len+1))
      }
    }
    if num/2 >= x && num%2 == 0 {
      let temp = lenStore[num/2, default: MAX]
      if len+1 < temp { // 횟수가 더 작을때만 업데이트 하고 큐에넣음
        lenStore[num/2] = len+1
        queue.append((num/2, len+1))
      }
    }
    if num/3 >= x && num%3 == 0 {
      let temp = lenStore[num/3, default: MAX]
      if len+1 < temp { // 횟수가 더 작을때만 업데이트 하고 큐에넣음
        lenStore[num/3] = len+1
        queue.append((num/3, len+1))
      }
    }
  }
  return x == y ? 0 : lenStore[x, default: -1]
}

❌ 틀린 이유 및 틀린 부분

• x와 y가 같은 경우 큐가 비게 되어 -1이 반환이 됨 → 결과를 반환하는 부분에 x와 y가 같은 경우 0을 반환추가
• 횟수가 작을때만 append가 이루어져야하는데 전체를 넣어서 시간초과 발생 → 횟수가 작을때만 append를 진행하게 수정

⏳ 시간 복잡도

• 최악의 상황 x = 1, y = 1000000, n = 1인 상황
• 전부 구하게되면 3의 (n-1)제곱의 계산이 들어가는 것같다 하지만 이전에 구했던 값을 저장해서 그 이하를 계산하지 않는다면 숫자 N에 대한 정보는 O(N)만에 구할 수 있다.

📌 풀이 또는 기억할 정보

• 다른 사람들의 풀이를 보니 그냥 x~y 반복을 돌면서 +n, x2, x3을 해도 괜찮았던거 같다