백준 - 0 만들기(Swift)

백준 - 0 만들기(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

 

 나의 풀이

 

처음 문제를 보고 테스트케이스와 N의 범위가 10이하인 것을 확인하고 +, -, 공백 3가지의 경우이기 때문에 DFS로 재귀를 돌려야겠다고 생각했다. 

 

구현을 하다가 파이썬의 eval함수가 스위프트에는 따로 내장되어있지 않아서 이를 어떻게 구현할지 고민해야했다.

그래서 숫자가 아닌것들과 숫자인 것들로 분리를 시킨 뒤 스택에 저장해서 연산을 하도록 했다.

 

마지막으로 아스키코드 순으로 출력이되어야 하기 때문에 result를 전역변수로 다뤄서 정렬할 수 있게끔 했다.

 

import Foundation

let tc = Int(readLine()!)!
var result: [String] = []
for _ in 0..<tc {
    let N = Int(readLine()!)!
    let arr = Array(1...N)    
    DFS(1, "1", arr)
    result.sort(by: <) // 아스키코드 순서를 위해 정렬
    result.forEach { print($0) }
    print()
    result = []
}

func DFS(_ L: Int, _ str: String, _ arr: [Int]) {
    if L == arr.count { // 끝에 도달했다면
        var stack: [Int] = [] // 계산할 공간
        var str2 = str.replacingOccurrences(of:" ", with:"") //공백을 없애서 숫자를 붙여준다.
        let nums = str2.split(whereSeparator: { !$0.isNumber })
        let seps = str2.split(whereSeparator: { $0.isNumber })
        var i = 0
        for x in nums {
            if stack.isEmpty {
                stack.append(Int(x)!)
            } else {
                let last = stack.removeLast()
                if seps[i] == "+" {
                    stack.append(last+Int(x)!)
                } else {
                    stack.append(last-Int(x)!)
                }
                i += 1
            }
        }
        if stack.last! == 0 { // 연산한 값이 0이라면
            result.append(str)
        }
         
    } else { 
        DFS(L+1, str + "+\(arr[L])", arr)
        DFS(L+1, str + "-\(arr[L])", arr)
        DFS(L+1, str + " \(arr[L])", arr)    
    }
}

\