카카오 재귀알고리즘 문제, 괄호변환 swift언어 문제풀이

 

 

 

오늘은 카카오 기출 알고리즘 문제 중, 재귀알고리즘 문제인 괄호변환문제를 풀어보도록 하겠습니다. 해당 문제에 대한 설명은 아래 링크를 참고하시면 되겠습니다. ▼

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

 

 

 

해당 문제는 문제에서 설명한 대로 재귀코드를 구현하여 올바른괄호 형태를 만들어주고 반환해주면 되는 문제로, 문제설명만 제대로 읽어서 그래도 구현해준다면 풀 수 있는 문제였습니다.

그럼 곧바로 swift언어를 사용해서 해당문제를 풀어보겠습니다.

 

 

 

 

 

---

카카오 재귀알고리즘 문제, 괄호변환 swift 언어 풀이

먼저 문제풀이에 필요한 기능을 몇개 Array extension에 구현해두었습니다. 본 문제의 입력값은 String 타입이지만, 저는 간편한 첨자접근 처리를 하기 위해 String 타입 입력값을 [Character] 타입 배열로 변환해서 풀었습니다. 

 

3 ~ 5행) [Character] 타입 배열을 String 타입으로 변환할때 사용할 toString 변수입니다.

7 ~ 18행) 올바른 괄호문자열인지 여부를 반환해주는 isValidBrace 변수를 구현했습니다. stack 원리를 이용해서 괄호가 올바른 형태로 여닫히는지를 판단하고 있습니다.

 

20 ~ 31행) 균형잡힌 괄호, U와 그 뒤의 V를 나누어 반환해주는 makeUV 메서드를 구현했습니다. 만약 leftCount + rightCount 가 원본 배열의 길이인 self.count와 동일하다면, V는 빈 배열을 반환하여 빈 문자열 값임을 확인할 수 있도록 해줍니다.

 

이제 이어서 solution 메서드를 구현해보겠습니다.

 

 

 

36행) 입력받은 문자열이 비여있으면 그대로 ""를 반환해줍니다. 문제에서 나온 설명대로 구현했습니다.

* String, Array 타입 모두 isEmpty의 시간복잡도는 O(1)입니다.

 

 

 

 

앞서 말했듯이, p 문자열을 Array타입으로 변환해서 사용했습니다. 균형잡힌 U문자 배열, V문자 배열을 makeUV() 메서드로 만들어 준후, 이후 재귀 동작을 구현할 준비를 합니다. V 배열은 이후에 solution 재귀 인자로 사용되어야 하므로 미리 String 타입의 vString으로 변환해주었습니다.

 

 

 

 

43 ~ 44행) U가 올바른 문자열일 경우, 올바른 문자열 U 뒤에 vString 문자열의 solution 재귀 반환값을 붙여서 그대로 반환해줍니다. 

45 ~ 51행) 만약 U가 올바른 문자열이 아닌경우, 문제 설명에서 나온 그대로 그에 맞는 올바른 괄호 구성 로직을 구현해줍니다. vString의 재귀 반환값 앞 뒤로 괄호를 감싸주고, U의 앞뒤 문자를 제거 + 각각의 괄호를 map 연산자로 반전처리한 문자열을 붙여서 반환해주고 있습니다.

 

이렇게 문제 설명 그대로 특정 로직을 통해 올바른 괄호를 만들어주는 solution 메서드를 완성할 수 있었습니다.

문제 제출결과 및 전체 소스코드는 아래와 같습니다. 언제든지 질문 및 의견 환영합니다. 즐거운 코딩 되시길 바랍니다. 😎

 

 

 

---

재귀알고리즘 문제, 괄호변환 스위프트언어 풀이 결과 ▼

---

괄호변환 스위프트언어 전체 소스코드 ▼

extension Array where Element == Character {
    var toString: String {
        return self.map { String($0) }.joined()
    }
    
    var isValidBrace: Bool {
        var stackCount: Int = 0
        for char in self {
            if char == "(" {
                stackCount += 1
            } else {
                if stackCount > 0 { stackCount -= 1 }
                else { return false }
            }
        }
        return stackCount == 0 ? true : false
    }
    
    func makeUV() -> ([Character], [Character]) {
        var leftCount: Int = 0
        var rightCount: Int = 0
        for char in self {
            if char == "(" { leftCount += 1 }
            else { rightCount += 1 }
            if leftCount == rightCount { break }
        }
        
        let U = Array(self[..<(leftCount+rightCount)])
        let V = (leftCount+rightCount) == self.count ? [] : Array(self[(leftCount+rightCount)...])
        return (U, V)
    }
}

func solution(_ p: String) -> String {
    if p.isEmpty { return "" }
    let stringArray = Array(p)
    let UV = stringArray.makeUV()
    var (U, V) = (UV.0, UV.1)
    let vString = V.toString
    if U.isValidBrace {
        return U.toString + solution(vString)
    } else {
        var answer: String = "(" + solution(vString) + ")"
        U.removeFirst()
        U.removeLast()
        answer += U.map { $0 == "(" ? ")" : "(" }.toString
        return answer
    }
}