[Swift] 백준 1248 - 맞춰봐

문제 바로가기

문제 이름부터,, 저돌적이다..

처음 생각한 풀이는 다음과 같다.
예를들어, N = 4이고 입력받은 문자열S가 "-+0++++--+"라면

"-+0+"
"+++"
"--"
"+"

S를 다음과 같이 N(4)개, N-1(3)개, N-2(2)개, 1개 씩 나눠야 한다.
이때 이 문자배열에 맞는 배열을 [a,b,c,d]라 하면

a = > '-' (S[0])
a + b => '+'
a + b + c = > '0'
a + b + c => '+'
이고
b => '+' (S[4])
b + c => '+'
b + c + d => '+'
이다

따라서 [a, b, c, d] 의 원소의 부호값은 S[0], S[0+4], S[0+4+3], S[0+4+3+2] 이므로

재귀함수의 매개변수를 사용하여

recur(0,0)

func recur(_ num: Int, _ idx: Int) {
    S[idx] -> num번째 원소의 부호값
    recur(num + 1, idx + (N-num))
    
}

다음과 같이 S[idx]로 원소의 부호값을 찾고,
해당 부호를 만족하는 원소배열이 완성되면(num == N)
S의 나머지 부호값을 확인하여 모두 성립하는 경우 출력하도록 하였다.

이를 코드로 표현하면 아래와 같다.

초기 풀이 (시간초과됨)

import Foundation

let N = Int(readLine()!)!
let arr = readLine()!
var Sarray = [Character]()

for char in arr {
    Sarray.append(char)
}

var result = [Int]()
var mode = true

func recur(_ num: Int, _ idx: Int) {
    
    if num == N {
        var start = 0
        for i in 0..<N {
            var sum = 0
            let end = start + (N-i)
            
            for j in start..<end {
                sum += result[i+(j-start)]
                
                if Sarray[j] == "+" && sum <= 0 { return }
                if Sarray[j] == "-" && sum >= 0 { return }
                if Sarray[j] == "0" && sum != 0 { return }
            }
            
            start = end
        }
        
        mode = false
        print(result.map{String($0)}.joined(separator: " "))
        return
    }
    
    
    for i in -10...10 {
        if mode == false {
            break
        }
        
        
        if Sarray[idx] == "-" {
            if i >= 0 {
                continue
            }
        } else if Sarray[idx] == "+" {
            if i <= 0 {
                continue
            }
        } else if Sarray[idx] == "0" {
            if i != 0 {
                continue
            }
        }
        
        for j in idx..<(idx + (N - num)) {
            if Sarray[j] == "-" {
                
            }
        }
        
        result.append(i)
        recur(num+1, idx + (N-num))
        result.removeLast()

    }
}

recur(0, 0)

완전 시간초과됨 ... 어디서 줄일 수 있는지도 모르겟음 ㅠㅜ

암튼 그래서 다른 분의 풀이를 봤는데
원소를 입력받을 때마다 가능한 S배열을 원소 부호값을 모두 점검한 뒤 모두 성립하는 원소만 배열에 추가하도록 하는 풀이를 보았다

그러니까 위 코드는
이 원소들의 부호값 S[0], S[4], S[7], S[9]만 성립한다면
배열에 넣어 S배열이 모두 성립하는지 확인 => 출력
이였는데

이번에는
[a,b] 에 c를 넣어 주기 전

• S[2] => a+ b + c 의 부호,
• S[5] => b+ c의 부호,
• S[7] => c의 부호

가 모두 성립하는 지 확인하고, 성립하는 경우 c를 넣고
배열의 원소가 다 채워지면 -> 출력 하는 방식이다.

따라서 두 가지 차이점을 가져야한다.

• 재귀함수 안에 S배열의 모든 경우가 성립하는지 체크하는 함수 check()
• S가 2차원 배열

- 2차원 S 배열

	0	1	2	3
0	-	+	0	+
1		+	+	+
2			-	-
3				+

• 2차원 S배열에는 부호들이 위와 같이 담겨있어야 한다.

- func check()

func check(_ idx: Int) -> Bool {
    var sum = 0
    for i in (0...idx).reversed() {
        sum += result[i]
    
       if S[i][idx] == "+" && sum <= 0 { return false }
       if S[i][idx] == "-" && sum >= 0 { return false }
       if S[i][idx] == "0" && sum != 0 { return false }
    }
    
    return true
}

• 모두 성립하는 경우 true를 반환하고 도중에 성립하지 않는 경우 false를 반환합니다.

최종 풀이

import Foundation

let N = Int(readLine()!)!
let arr = readLine()!
var S :[[Character]] = Array(repeating: Array(repeating: "a", count: 11), count: 11)

var idx = 0
for i in 0..<N {
    for j in i..<N {
        let arrIdx = arr.index(arr.startIndex, offsetBy: idx)
        Sarray[i][j] = arr[arrIdx]
        idx += 1
    }
}
var result = [Int]()
var mode = true

func check(_ idx: Int) -> Bool {
    var sum = 0
    for i in (0...idx).reversed() {
        sum += result[i]
    
       if S[i][idx] == "+" && sum <= 0 { return false }
       if S[i][idx] == "-" && sum >= 0 { return false }
       if S[i][idx] == "0" && sum != 0 { return false }
    }
    
    return true
}

func recur(_ num: Int) {
    if num == N {
        mode = false
        print(result.map{String($0)}.joined(separator: " "))
        return
    }
    
    for i in -10...10 {
        if !mode {
           break
        }
        
        result.append(i)
        if check(num) {
            recur(num + 1)
        }
        result.removeLast()
    }
}

recur(0)