[Algorithm] 괄호 변환

[hwangJi-dev]

💬 Idea

• 다른 수를 써서 문제를 풀이하기보다, 문제 내에서 안내한 방법대로 구현한다면 풀 수 있었던 문제.
• “재귀함수”를 사용하자.
• 동작 단위로 함수를 잘 분리하자.
  • 1️⃣  주어진 문자열을 두 “균형잡힌 괄호 문자열” u,v로 분리하는 함수
  • 2️⃣  문자열이 “올바른 괄호 문자열”인지 판별하는 함수
  • 3️⃣  문자열을 “올바른 괄호 문자열”로 고치는 함수

💬 풀이

func solution(_ p:String) -> String {
    var answer = ""
    
    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if p == "" {
        return ""
    }
    
    // 2. 문자열을 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    let u = makeBalanceBracket(p)[0]
    let v = makeBalanceBracket(p)[1]
    
    // 3. 문자열 u가 "올바른 괄호 문자열" 이라면
    if checkRightBracket(u) == true {
        // answer에 u를 이어 붙인다.
        answer += u
        if v != "" {
            // 문자열 v에 대해 1단계부터 다시 수행합니다.
            // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
            return answer + solution(v)
        }
    } else {
        // 문자열 u가 "올바른 괄호 문자열"이 아닐 때
        // ✅ 4번 과정 수행
        answer += fixToRightBracket(u, v)
    }
    
    return answer 
}

// MARK: - 문자열을 "균형잡힌 괄호 문자열"로 분리하여 return하는 함수
func makeBalanceBracket(_ p: String) -> [String] {
    var sum = 0
    var splitIndex = 0
    let bracket = Array(p).map { String($0) }
    
    for (index, bracket) in bracket.enumerated() {
        sum += bracket == "(" ? -1 : 1
        
        if sum == 0 {
            splitIndex = index
            break
        }
    }
    
    var u = ""
    var v = ""
    
    if splitIndex < p.count {
        u = String(p[String.Index(utf16Offset: 0, in: p)...String.Index(utf16Offset: splitIndex, in: p)])
        v = String(p[String.Index(utf16Offset: splitIndex + 1, in: p)..<p.endIndex])
    }
    
    return [u, v]
}

// MARK: - "올바른 괄호 문자열"인지 판별하는 함수
func checkRightBracket(_ p: String) -> Bool {
    var sum = 0
    let bracket = Array(p).map { String($0) }
    
    for i in bracket {
        if sum == 0 && i == ")" {
            return false
        }
        sum += i == "(" ? -1 : 1
    }
    
    return sum != 0 ? false : true
}

// MARK: - 문자열이 "올바른 괄호 문자열"이 아닐 때 수행되는 fix 함수
func fixToRightBracket(_ u: String, _ v: String) -> String {
    var u = Array(u).map { String($0) }
    
    // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
    var bracket = "("
    
    // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
    bracket += solution(v)
    
    // 4-3. ')'를 다시 붙입니다.
    bracket += ")"
    
    // 4-4. u의 첫 번째와 마지막 문자를 제거하고,
    u.removeFirst()
    u.removeLast()
    
    // 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
    for i in u {
        bracket += i == "(" ? ")" : "("
    }
    
    // 4-5. 생성된 문자열을 반환합니다.
    return bracket
}

소요시간 : 3시간

💬 알게된 것

• 구현 방법에 대해 문제에 제시해준 것이 있다면 그대로 차근차근 풀어보자. !!!
  • 풀이 방법을 다 준 것이나 다름없다.
• 재귀함수의 사용법에 대해서 조금이나마 익히게 된 것 같다.
• 예전 자료구조 수업 들을 때 재귀함수를 좋아했던 것이 새록새록 떠오른다..~