[Swift/프로그래머스] N으로 표현 ( 그리디 , 연산 )

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

프로그래머스

 

이전에 풀었던 dp 방식으로 해결하려했는데 시간초과 및 오답이 나왔다.

 

첫번째 풀이

import Foundation
func solution(_ N: Int, _ number: Int) -> Int {
    if N == number {
        return 1
    }
    
    // 배열 크기를 적절한 값으로 제한
    let maxSize = 32001  // 충분히 큰 적절한 값으로 설정
    var dp = [Int](repeating: Int.max, count: maxSize)
    
    dp[N] = 1  // 0이 아닌 1로 시작
    
    for i in 0..<maxSize {
        if dp[i] == Int.max { continue }
        if dp[i] >= 8 { continue }  // 8번 제한
        
        // 범위 체크를 추가하여 배열 범위를 벗어나지 않도록 함
        if i + N < maxSize {
            dp[i + N] = min(dp[i + N], dp[i] + 1)
        }
        if i - N > 0 {
            dp[i - N] = min(dp[i - N], dp[i] + 1)
        }
        if i * N < maxSize {
            dp[i * N] = min(dp[i * N], dp[i] + 1)
        }
        if i != 0 && i % N == 0 {
            dp[i / N] = min(dp[i / N], dp[i] + 1)
        }
        
    }
    
    
    // number가 범위를 벗어나거나 도달할 수 없는 경우
    if number >= maxSize || dp[number] == Int.max || dp[number] > 8 {
        return -1
    }
    
    return dp[number]
}

 

이전에 풀었던 문제 ( https://100percent-me.tistory.com/entry/Swift%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%AB%EC%9E%90-%EB%B3%80%ED%99%98%ED%95%98%EA%B8%B0-%EA%B7%B8%EB%A6%AC%EB%94%94 )

[Swift/프로그래머스] 숫자 변환하기 ( 그리디 )

 

에서는 나눗셈과 뺄셈이 없기에 목표 숫자를 넘어가면 return을 해주면 되기에 시간초과가 발생하지 않지만.

 

해당 문제에서는 방문했던숫자를 또 방문하기때문애 안되는 것 같다.

 

추가적으로

 

12 = (55 + 5) / 5

 

이 테스트케이스를 만족하지 못해서 그런것 같다.

 

그래서 55, 555와 같은 경우를 따로 설정해주면 되지 않을까? 라는 생각을 해보았다.

import Foundation

func solution(_ N: Int, _ number: Int) -> Int {
    if N == number {
        return 1
    }
    
    let maxSize = number * N + 1  // +1을 추가하여 경계값 처리
    var dp = [Int](repeating: Int.max, count: maxSize)
    
    dp[N] = 1  // N 하나로 만드는 경우
    
    // 연속된 숫자 처리 (NN, NNN, NNNN 등)
    var continuousN = N
    for i in 2...8 {  // 8번까지만 시도
        continuousN = continuousN * 10 + N
        if continuousN < maxSize {
            dp[continuousN] = i
        }
    }
    ...
}

 

 

슬프도다.. 슬프도다..

 

Set을 이용한 풀이

대부분의 사람들이 이렇게 풀이했다.

8번이 넘어가면 -1을 return 하기에 이런식으로 풀어도 괜찮나보다

import Foundation

func solution(_ N: Int, _ number: Int) -> Int {
    if N == number {
        return 1
    }
    
    var dp = [Set<Int>](repeating: Set<Int>(), count : 9)
    
    for i in 1...8{
        
        var continuousN = 0
        for _ in 0..<i{
            continuousN = continuousN * 10 + N
        }
        dp[i].insert(continuousN)
        
         for j in 1..<i {
            for op1 in dp[j] {
                for op2 in dp[i-j] {
                    dp[i].insert(op1 + op2)
                    dp[i].insert(op1 - op2)
                    dp[i].insert(op1 * op2)
                    if op2 != 0 {
                        dp[i].insert(op1 / op2)
                    }
                }
            }
        }
         if dp[i].contains(number) {
            return i
        }
    }
    return -1
}