[프로그래머스] Swift 2020 카카오 괄호변환

문제 :

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

코딩테스트 연습 - 괄호 변환

난이도 : level2

 

분석 : 

주어진 요건을 잘 읽고 요구 사항대로 구현하는 문제였다. 이런 문제일수록 설계를 잘 하지 않으면 로직이 꼬이기 쉬워 어려운거 같다(나한테만 일지도 모른다 .. ㅎ) 

1,2,3,4번을 차례대로 구현해주되 필요한건 함수로 분리해 작성하는것이 좋다 판단 들었다.

따라서 1번은 isEmpty로 검사하였다.

2번은 recursive 함수 안에서 모든 문자열을 돌며 "(" 수와 ")"수를 비교해 같을때(균형잡힌 괄호 문자열) u, 그 이후의 문자를 v로 분리하였다.

3번은 check()함수를 통해 올바른 괄호 문자열인지 확인한다. 검사할 문자열 첫번째 원소부터 "("일 경우 stack에 넣고, ")"일 경우 stack에 쌓인 문자가 "("인지 확인하며 O(n)의 시간 복잡도를 가진다.

4번은 올바른 문자가 아닐경우 분기하여 처리한다. 이 경우를 이해하지 못해 다른 블로그를 참고하여 풀었다 !! 

newString 변수를 하나 만들어 "("를 붙인 뒤 4-2번을 수행할때 v를 재귀를 거쳐 올바른 문자열로 바꾼다. 그 뒤 ")"를 붙이고 

4-4번인 u의 첫번째, 마지막 문자를 제거한뒤 u 스트링의 원소를 "(" -> ")", ")" -> "("로 바꿔 newString 뒤에 바꾼 원소들을 붙여 반환한다.

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/14.
//

import Foundation

func check(_ s: String) -> Bool {
    if s.isEmpty { return true }
    var s = s
    var stack = [String]()
    
    while !s.isEmpty {
        let x = String(s.removeFirst())
        if stack.isEmpty {
            stack.append(x)
        }else if stack.last! == "(" && x == ")" {
            stack.removeLast()
        }else {
            stack.append(x)
        }
    }
    return stack.isEmpty
}

func recursive(_ p: String) -> String {
    if p.isEmpty { return "" }
    else if check(p) {
        return p
    }
    
    var leftCnt = 0
    var rightCnt = 0
    var u = ""
    var v = ""
    for (idx, i) in p.enumerated() {
        if i == "(" {
            leftCnt += 1
            u += "("
        }else if i == ")" {
            rightCnt += 1
            u += ")"
        }
       
        if leftCnt == rightCnt {
            v = p.substring(from: idx+1, to: p.count-1)
            if(check(u)) { // 올바른 문자열인지
                return u + recursive(v)
            }else { // 올바른 괄호 문자열이 아니므로
                let newString = "(" + recursive(v) + ")"
                u.removeFirst()
                u.removeLast()
                //나머지 괄호 방향 뒤집기
                u = u.map {
                    if $0 == "(" { return ")" }
                    else { return "(" }
                }.reduce(""){$0 + $1}
                return newString + u

            }
        }
    }
    
    return ""
}

func solution(_ p:String) -> String {
    return recursive(p)
}

extension String {
    func substring(from: Int, to: Int) -> String {
        guard from < count, to >= 0, to - from >= 0 else {
            return ""
        }
        // Index 값 획득
        let startIndex = index(self.startIndex, offsetBy: from)
        let endIndex = index(self.startIndex, offsetBy: to + 1)
        
        // 파싱
        return String(self[startIndex ..< endIndex])
    }
}

결과 :