[Algorithm] N으로 표현

[hwangJi-dev]

💬 문제

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

💬 Idea

• dp는 불필요한 연산을 줄이기 위해 사용되는 알고리즘이므로 연산 결과를 dict에 저장하자
• 새로 나온 숫자가 있는 경우에 해당 최솟값이 8 이하일 경우에만 queue에 숫자를 추가한다.
• queue가 빌 때까지 반복한다.

💬 풀이

enum operators: Int {
    case plus = 1
    case minus = 2
    case mul = 3
    case div = 4
}

func solution(N:Int, number:Int) -> Int {
    var nCntDict: [Int: Int] = [:]
    var queue: [Int] = []
    
    for i in 1...String(number).count {
        let n = Int(String(repeating: String(N), count: i))!
        nCntDict[n] = i
        queue.append(n)
    }
    
    queue = queue.reversed().map({ Int($0) })
    
    while !queue.isEmpty {
        let q = queue.removeFirst()
        
        for i in 1...4 {
            var n = q
            switch operators(rawValue: i) {
            case .plus:
                n = q + N
            case .minus:
                n = q - N
            case .mul:
                n = q * N
            default:
                n = q / N
            }
            
            if n > 0 {
                if nCntDict[n] == nil {
                    nCntDict[n] = nCntDict[q]! + 1
                    if nCntDict[q]! + 1 <= 8 {
                        queue.append(n)
                    }
                } else {
                    if nCntDict[q]! + 1 < nCntDict[n]! {
                        if nCntDict[q]! + 1 <= 8 {
                            queue.append(n)
                        }
                        nCntDict[n] = nCntDict[q]! + 1
                    } else {
                        nCntDict[n] = nCntDict[n]!
                    }
                }
            }
        }
        
        if nCntDict[number] != nil { break }
    }
    
    return nCntDict[number] ?? -1
}

소요시간 : 40분

• 정확성 44.4 퍼센트가 나와 재풀이에 들어갔다.

💬 Idea2

dp의 원리를 더 이용해야한다.

문제에서 최대 연산 횟수가 8이라고 지정해줬으므로 dp를 사용하기 적합하다.

<원리>

• dp[2] ⇒ 나올 수 있는 조합 1, 1 / 2 (이 경우 55와 같은 자릿수만큼의 N 추가)
• dp[3] ⇒ 나올 수 있는 조합 1,2 / 2,1 / 3 (555)
• dp[4] ⇒ 나올 수 있는 조합 1,3 / 2,2 / 3,1 / 4 (5555)

1 ~ 8 까지 나올 수 있는 조합별 사칙연산 결과를 dp 배열에 저장한다.

이 때, targetNumber와 같은 숫자가 나온다면 result에 연산 횟수의 최솟값을 갱신한다.

💬 풀이2

import Foundation

func solution(N:Int, number:Int) -> Int {
    var dp = Array(repeating: Set<Int>(), count: 9)
    var result = Int.max
    
    for i in 1..<9 {
        for j in 1..<i {
            for k in dp[i - j] {
                for l in dp[j] {
                    // +
                    dp[i].insert(k + l)
                    
                    // -
                    if k - l > 0 {
                        dp[i].insert(k - l)
                        if k - l == number { result = min(result, i) }
                    }
                    
                    // *
                    dp[i].insert(k * l)
                    
                    // /
                    if l != 0 && k != 0 {
                        dp[i].insert(k / l)
                        if k / l == number { result = min(result, i) }
                    }
                    
                    if k + l == number || k * l == number { result = min(result, i) }
                }
            }
        }
        
        let nstr = Int(String(repeating: "\(N)", count: i))!
        dp[i].insert(nstr)
        if nstr == number { result = min(result, i) }
    }
    
    return result == Int.max ? -1 : result
}