[Swift] 프로그래머스(Lv3) - N으로 표현

안녕하세요 :)

https://programmers.co.kr/learn/courses/30/lessons/42895

풀이

N이 number일 경우 사칙연산이 필요없으므로 바로 1을 return 합니다.

DFS로 구현해서 0부터 시작하여 사칙연산(+ - * /)을 수행합니다.

DFS 종료조건
1) N 사용횟수 count가 8보다 크면 종료합니다.
2) 현재 숫자인 now와 number가 같다면 종료합니다.
이때, answer는 count의 최소값으로 업데이트 합니다.

555 -> 5를 3번 사용한 숫자 입니다.
이런 숫자들을 처리하기 위해 for문을 돌면서
NN = NN * 10 + N을 해줍니다.
(NN이 5 -> 55 -> 555 ... 되도록)

import Foundation

func solution(_ N:Int, _ number:Int) -> Int {
    if N == number {
        return 1
    }
    
    var answer: Int = -1
        
    func dfs(_ count: Int, _ now: Int) {
        if count > 8 { return }
        if now == number {
            if count < answer || answer == -1 {
                answer = count
            }
            return
        }
        
        var NN = 0
        for i in 0..<8 {
            if answer != -1 && answer < count + 1 + i {
                break
            }
            NN = NN*10 + N
            dfs(count + 1 + i, now + NN)
            dfs(count + 1 + i, now - NN)
            dfs(count + 1 + i, now * NN)
            dfs(count + 1 + i, now / NN)
        }
    }
    
    dfs(0, 0)
    
    return answer
}