문자열, 재귀_백준_2800 swift

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

2800번: 괄호 제거

 

문제 접근

1. 입력받은 input에서 괄호 쌍의 인덱스를 저장
2. input을 임시변수 temp에 저장하여, 괄호 쌍을 공백문자로, Set sol에 insert하는 반복문
3. 반복문 내부에서 temp를 재귀, 결과를 sol = sol.union(재귀 return값)
4. sol은 Set이기에, 중복이 제거 될 것
5. return받은 Set의 element인 String의 공백을 제거한 뒤, sorted(), print()

오답 코드

결과 : 시간초과

예상 원인 : 반복문 내부에 재귀가 있는 것.

import Foundation

let input = readLine()!

class BracketPair {
        var open: Int
        var close: Int
        
        init(open: Int, close: Int) {
            self.open = open
            self.close = close
        }
        convenience init() {
            self.init(open: 0, close: 0)
        }
}

func solution(_ str: String) -> [String] {
        let result = recursion(str)
        
        let removedWhiteSpace = result.map({ word -> String in
            var temp = word
            temp.removeAll(where: {$0 == " "})
            return temp
        }).sorted()
        
        return removedWhiteSpace
    }
    
func recursion(_ str: String, _ bracketPairList: [BracketPair] = []) -> Set<String> {
        var sol = Set<String>()
        var bracketList = bracketPairList
        
        
        if bracketList.isEmpty {
            var stack = [Int]()
            for (n,c) in str.enumerated() {
                if c == "("{
                    stack.append(n)
                } else if c == ")" {
                    let open = stack.removeLast()
                    bracketList.append(BracketPair.init(open: open, close: n))
                }
            }
        }
        
        for i in 0..<bracketList.count {
            var temp = str
            
            if bracketList.isEmpty {
                break
            }
            
            let bracket = bracketList.removeLast()
            
            let openIndex = bracket.open
            let closeIndex = bracket.close
            
            let open = str.index(str.startIndex, offsetBy: openIndex)
            let close = str.index(str.startIndex, offsetBy: closeIndex)
            
            temp.remove(at: close)
            temp.insert(" ", at: close)
            temp.remove(at: open)
            temp.insert(" ", at: open)
            
//            print(i, openIndex, closeIndex, temp)
            sol.insert(temp)
            sol = sol.union(recursion(temp, bracketList))
        }
        
        return sol
    }

let result = solution(input)
for str in result {
    print(str)
}

 

개선 but 오답

개선 사항 : 공백문자를 사용하는 경우, 같은 경우를 못 잡아내는 경우가 있었다. 이를 해소하기 위해 공백 제거 후 Set 변환을 했다.

문제 사항 : 시간초과 재 발생. 설계자체 성능의 문제인듯,,,

 

코드 

class Baek2800 {
    
    class BracketPair {
        var open: Int
        var close: Int
        
        init(open: Int, close: Int) {
            self.open = open
            self.close = close
        }
        convenience init() {
            self.init(open: 0, close: 0)
        }
    }
    
    func solution(_ str: String) -> [String] {
        let result = recursion(str)
        
        let removedWhiteSpace = result.map({ word -> String in
            var temp = word
            temp.removeAll(where: {$0 == " "})
            return temp
        })
        
        return Set(removedWhiteSpace).sorted()
    }
    
    func recursion(_ str: String, _ bracketPairList: [BracketPair] = [], _ history: [Bool] = []) -> Set<String> {
        var sol = Set<String>()
        var bracketList = bracketPairList
        var nowHistory = history
        
        if bracketList.isEmpty {
            var stack = [Int]()
            for (n,c) in str.enumerated() {
                if c == "("{
                    stack.append(n)
                } else if c == ")" {
                    let open = stack.removeLast()
                    bracketList.append(BracketPair.init(open: open, close: n))
                }
            }
        }
        
        if nowHistory.isEmpty {
            nowHistory = [Bool].init(repeating: false, count: bracketList.count)
        }
        
        for i in 0..<bracketList.count {
            if bracketList.isEmpty {
                break
            }
            
            if nowHistory[i] == true {
                continue
            }
            var temp = str
            
            let bracket = bracketList[i]
            nowHistory[i] = true
            
            let openIndex = bracket.open
            let closeIndex = bracket.close
            
            let open = str.index(str.startIndex, offsetBy: openIndex)
            let close = str.index(str.startIndex, offsetBy: closeIndex)
            
            temp.remove(at: close)
            temp.insert(" ", at: close)
            temp.remove(at: open)
            temp.insert(" ", at: open)
            
//            print(i, openIndex, closeIndex, temp)
            sol.insert(temp)
            sol = sol.union(recursion(temp, bracketList, nowHistory))
        }
        
        return sol
    }
}