Programmers - 괄호 변환

프로그래머스 - 카카오2020 - 괄호 변환

문제

• '(', ')' 의 개수가 같다면 균형잡힌 괄호 문자열 이다.
• 올바른 괄호 문자열을 리턴하라

조건

• p는 '(', ')'로만 이루어진 2 <= p <= 1000 짝수
• 개수는 항상 같다.
• 이미 올바른 괄호 문자열 이라면 그대로 return

풀이

• 순서대로 조건을 수행하며 풀어본다.

코드(Swift)

extension String {
    func substr(startIndex: Int, length: Int?) -> String{
        if(startIndex >= self.count) {
            return ""
        }
        let start = self.index(self.startIndex, offsetBy: startIndex)
        if let length = length {
            let end = self.index(start, offsetBy: length)
            return String(self[start ..< end])
        } else {
            return String(self[start...])
        }
    }
}

func divideBalancedStr(str: String) -> (String, String){
    var charStack = Array<Character>()
    var offset = 1;
    charStack.append(str[str.startIndex])

    while !charStack.isEmpty && offset < str.count {
        let index = str.index(str.startIndex, offsetBy: offset)
        let char = str[index]
        if charStack.last! == char {
            charStack.append(char)
        } else {
            _ = charStack.popLast()
        }
        offset += 1
    }

    let u = str.substr(startIndex: 0, length: offset)
    let v = str.substr(startIndex: offset, length: nil)

    return (u, v)
}

func checkCorrectStr(str: String) -> Bool{
    // 가장 처음 ')' 이 오면 false
    if str[str.startIndex] == ")" {
        return false
    }

    return true
}
func overStr(str: String) -> String {
    var result = ""
    str.enumerated().forEach { (index, char) in
        if index == 0 || index == str.count-1 {
            return
        }

        if char == "(" {
            result += ")"
        } else {
            result += "("
        }
    }

    return result
}

func solution(_ p:String) -> String {
    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if p.count == 0 {
        return ""
    }
    // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    let (u, v) = divideBalancedStr(str: p)


    // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    if checkCorrectStr(str: u) {
        return u + solution(v)
    } else { // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
        // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
        var tempStr = "("
        // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        tempStr += solution(v)
        // 4-3. ')'를 다시 붙입니다.
        tempStr += ")"
        // 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        tempStr += overStr(str: u)
        // 4-5. 생성된 문자열을 반환합니다.
        return tempStr
    }
}

주의 사항

• 주어진 조건대로 푸는 문제이다. 조건을 잘 생각하면서 차근차근하면 된다.
• '(', ')' 괄호 문제는 보통 Stack을 활용하면 된다.
• Swift에는 Substr이 없기 때문에 이를 만들어 Extention 해서 쓴다.