[Swift 알고리즘] 프로그래머스(Lv.2) - 괄호 변환 / 2020 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 괄호 변환" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 구현 문제입니다.

저는 재귀와 스택을 이용해 해결했고 메서드 별로 설명을 드리겠습니다.

 

solution()

input을 받고 결과를 출력합니다. input p가 "" 이거나 "올바른 괄호 문자열"이라면 바로 p를 return합니다.

아니라면 재귀 메서드인 makeCorrectedString()를 시작합니다!

 

makeCorrectedString()

문제에 기술되어 있는 로직을 실행하는 메서드입니다.

 

1. splitUV()를 이용해 input을 u와 v로 나눕니다. splitUV()에 대해서는 아래 설명이 있습니다.

2. 만약 u가 "올바른 괄호 문자열"이라면 u + makeCorrectedString(v)를 return합니다. (문제 3번 과정)

3. 만약 u가 "올바른 괄호 문자열"이 아니라면 v에 대해서 올바른 괄호 문자열을 구하고 문제의 4번 과정을 실행합니다.

 

splitUV()

input string을 u와 v로 나눠서 tuple로 return하는 메서드입니다.

u와 v는 스택을 이용했는데요.

스택에 한 글자씩 넣으면서 지금까지 스택의 문자열이 "균형잡힌 괄호 문자열"인지 확인합니다.

만약 "균형잡힌 괄호 문자열"이라면 이 문자열을 u로, 이후의 문자열을 v로 설정하고 return 합니다.

 

isBalance()

"균형잡힌 괄호 문자열"인지 확인합니다.

filter 고차함수를 사용해서 "("의 개수와 ")"의 개수가 동일한지 체크하고 Bool 타입을 return합니다.

 

isCorrectly()

"올바른 괄호 문자열"인지 확인합니다.

스택을 이용해 괄호가 완성되면 stack을 pop을 합니다. 마지막에 stack이 비어있지 않다면 올바른 괄호 문자열이 아닙니다.

 

끝!

사실 문제의 로직대로 코드를 작성하면 되서 설명이 의미가 있는지 잘 모르겠습니다.

재귀를 이용하는 부분이 살짝 까다로웠지만 난이도 자체는 어렵지 않았던 것 같습니다.

 

감사합니다! 

 

---

전체 코드

import Foundation

func isCorrectly(_ p: String) -> Bool {
    if p.isEmpty { return true }
    
    var stack: [String] = []

    for str in p {
        let str = String(str)
        if stack.isEmpty {
            stack.append(str)
        } else {
            if str == ")" && stack.last! == "(" {
                stack.popLast()
            } else {
                stack.append(str)
            }
        }
    }
    
    return stack.isEmpty
}

func isBalance(_ p: [String]) -> Bool {
    if p.isEmpty { return true }

    return p.filter { $0 == "(" }.count == p.filter { $0 == ")" }.count
}

func splitUV(_ p: String) -> (String, String) {
    var stack: [String] = []
    
    for str in p {
        let str = String(str)
        
        if stack.isEmpty {
            stack.append(str)
        } else {
            if isBalance(stack) {
                break
            } else {
                stack.append(str)
            }
        }
    }
    
    let u = stack.joined()
    let v = (stack.count == p.count) ? "" : String(p.suffix(p.count - stack.count))
    
    return (u, v)
}

func makeCorrectedString(_ string: String) -> String {
    if string.isEmpty {
        return ""
    }
    
    let (u, v) = splitUV(string)
    if isCorrectly(u) {
        return u + makeCorrectedString(v)
    } else {
        let str = "(" + makeCorrectedString(v) + ")"
        let u2 = (Array(u)[1..<u.count-1]).map { String($0) == ")" ? "(" : ")" }.joined()
        return str + u2
    }
}

func solution(_ p:String) -> String {
    if p.isEmpty || isCorrectly(p) {
        return p
    }
    
    let result = makeCorrectedString(p)
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.