[프로그래머스/Swift] 60058번 - 괄호 변환

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60058

💡 구현 아이디어

이번 문제는 문제에서 주어진 내용을 그대로! 작성하면 되어서 따로 구현 아이디어는 없다

사소한 부분으로 있다면 최근 각 기능을 함수로 분리시켜서 문제를 풀고 있는데 훨씬 편해진것같다

💻 코드

import Foundation

func solution(_ p:String) -> String {
    // let p = "))(("
    var result: [String] = Array(p).map{ String($0) }
    
    // 올바른 문자열이 아니면 변환 과정을 거침
    if !isCorrect(result) {
        result = recursiveCheck(result)
    }
    
    return result.joined()
}

func recursiveCheck(_ arr: [String]) -> [String] {
    var result: [String] = []
    if arr.isEmpty { return result } // 1

    let divP = divideStr(arr) // 2
    if isCorrect(divP.u) {
        result.append(contentsOf: divP.u)
        result.append(contentsOf: recursiveCheck(divP.v)) // 3-1
    } else {
        result.append("(") // 4-1
        result.append(contentsOf: recursiveCheck(divP.v)) // 4-2
        result.append(")") // 4-3
        var tempU = divP.u
        // 첫번째, 마지막 문자를 제거 해야함
        if !tempU.isEmpty {
            tempU.popLast()
            tempU.removeFirst()
        }
        
        // 4-4
        for val in tempU {
            let inp = (val == "(" ? ")" : "(")
            result.append(inp)
        }
    }
    
    return result // 3-1 , 4-5
}

// u와 v로 분리
func divideStr(_ arr: [String]) -> (u: [String], v: [String]) {
    if arr.isEmpty { return (u: [], v: []) }
    
    var u: [String] = []
    var v: [String] = []
    var flag: Bool = false // false : u에 저장, true : v에 저장
    var balance: Int = 0
    
    for idx in 0..<arr.count {
        balance += (arr[idx] == "(" ? 1 : -1)
        
        if flag {
            v.append(arr[idx])
        } else {
            u.append(arr[idx])
        }
        if balance == 0 { // 현재 idx 까지가 첫 균형잡힌 문자열
            flag = true
        }
    }
    return (u: u, v: v)
}

// 올바른 문자열인지 판별
func isCorrect(_ arr: [String]) -> Bool {
    var stack: [String] = []
    
    for p in arr {
        if p == "(" {
            stack.append("(")
        } else if stack.isEmpty {
            return false 
        } else {
            stack.popLast() 
        }
    }
    return true
}

❌ 틀린 이유 및 틀린 부분

• 4-4에서 앞뒤 문자를 제거한 뒤 괄호의 방향을 뒤집어야하는데 문자열의 방향을 뒤집어서 틀렸다

⏳ 시간 복잡도

O(n) : 최악의 경우 recursiveCheck에서 p를 각 한자리를 전부 확인함

📌 풀이 또는 기억할 정보

func solution(_ p:String) -> String {
    if p.count < 1 {return ""}

    var count = 0, index = p.startIndex
    repeat{
        count += String(p[index]) == "(" ? 1 : -1
        index = p.index(after: index)
    } while count != 0

    var u = String(p[..<index]), v = String(p[index...])
    if String(u.first!) == "("{
        return u + solution(v)
    }else{
        u.removeLast()
        u.removeFirst()
        return "(\\(solution(v)))\\(u.map{String($0) == "(" ? ")" : "("}.joined())"
    }
}

• 올바른 문자열인지를 판별하는 내용을 String(u.first!) == "(" 와 같이 작성하였다. - 실제로 균형 잡힌 문자열에서 시작이 “(”이면 올바른 문자열이 된다…
• 평소 재귀 함수를 쓰거나 할때 solution함수 자체를 재귀로 쓰려고 생각하지 않았는데 이렇게 작성하니 깔끔한 것 같다
• u, v로 분리하는 방식 또한 배열로 쪼개지 않고 문자열로 풀었다는 것이 차이가 발생한 부분인것 같다. 매번 문자열이 들어오면 배열로 쪼개서 쓰고 있는데 이는 C++로 문제를 푸는 습관이 아직 많이 남은 것 같다. 다음엔 문자열 자체를 가지고 문제를 풀어야겠다