재귀, 문자열_카카오기출_프로그래머스_괄호 변환 swift

문제 링크

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

 

문제 접근

문제 출제에 자세히 설명되어있다. 라고 하지만, 나는 처음에 이해를 잘 못했다.

오답코드가 작성된 이후에 블로그 글을 작성하는데, 나도 왜 저렇게 이해했는지 모르겠다. 주의가 산만한 상황에서 쫓기듯 풀어서 그런듯 하다.

 

1. p를 두개의 String u, v 로 분리한다.
2. 이 때, u 는 더 이상 분리 할 수 없어야한다. 이를 위해 counter를 사용하여 더 이상 분리 할 수 없는 지점을 찾아냈다.
3. u가 정상인지 아닌지와 무관하게 v는 올바른 괄호쌍이 되어야한다. 이를 위해 재귀를 사용한다.
4. u가 정상이라면, u의 뒤편에 정상화된 v를 붙여 return
5. u가 정상이 아니라면, 문제에 저술된 로직을 따른다.
   1. 첫번째 글자는 ) 이다.
   2. 정상화 된 v + ) 를 붙인다.
   3. u의 맨 앞과 뒤를 제거하고, ( -> )로, ) -> ( 로 변환하여 2의 뒤에 붙여 return.

 

 

오답 코드

import Foundation


func solution(_ p:String) -> String {
    
    func modifyFirstNEnd(_ str: String) -> String {
        var sol = "("
        
        let firstIndex = str.index(after: str.startIndex)
        var temp = str[firstIndex...]
        temp.removeLast()
        
        for char in temp {
            if char == "(" {
                sol.append(")")
            } else {
                sol.append("(")
            }
        }
        sol.append(")")
        
        return sol
    }
    
    func isRight(_ str: String) -> Bool {
        var counter = 0
        
        guard let first = str.first else {
            return true
        }
        
        if first == ")" {
            return false
        }
        
        for i in str {
            if i == "(" {
                counter += 1
            } else {
                counter -= 1
            }
            
            if counter < 0 {
                break
            }
        }
        
        if  counter < 0 {
            return false
        }
        
        return true
    }
    
    func recursion(_ str: String, _ flag: Bool = false) -> String {
        var counter = 0
        var u = ""
        var sol = ""
        var problemFlag = flag
        var str = str
        if problemFlag == true {
            problemFlag = false
            str = modifyFirstNEnd(str)
        }
        
        for (n,i) in str.enumerated() {
            print(counter, n, i, str)
            if i == "(" {
                counter += 1
            } else {
                counter -= 1
            }
            
            if counter == 0 {
                let index = str.index(str.startIndex, offsetBy: n)
                let nextIndex = str.index(after: index)
                var v = String()
                if problemFlag {
                    u = String(str[nextIndex...])
                    if !isRight(u) {
                        u = recursion(u)
                    }
                    v = String(str[...index])
                    print("u: \(u), v: \(v)")
                    sol = recursion(v,problemFlag) + u
                } else {
                    u = String(str[...index])
                    if !isRight(u) {
                        u = recursion(u)
                    }
                    v = String(str[nextIndex...])
                    print("u: \(u), v: \(v)")
                    sol = u + recursion(v,problemFlag)
                }
                
                
                break
            }
            
            if counter <= -1 {
                problemFlag = true
            }
        }
        return sol
    }
    
    
    
    return recursion(p)
    
}

와 정확도

테스트 1 〉	통과 (0.06ms, 16.5MB)
테스트 2 〉	실패 (0.09ms, 16.3MB)
테스트 3 〉	통과 (0.09ms, 16.3MB)
테스트 4 〉	실패 (0.08ms, 16.3MB)
테스트 5 〉	통과 (0.06ms, 16.2MB)
테스트 6 〉	통과 (0.09ms, 16.2MB)
테스트 7 〉	실패 (0.09ms, 16.2MB)
테스트 8 〉	통과 (0.07ms, 16.2MB)
테스트 9 〉	실패 (0.09ms, 16.4MB)
테스트 10 〉	실패 (0.09ms, 16.2MB)
테스트 11 〉	실패 (0.09ms, 16.4MB)
테스트 12 〉	실패 (0.09ms, 16.1MB)
테스트 13 〉	실패 (0.08ms, 16.4MB)
테스트 14 〉	실패 (0.08ms, 16.2MB)
테스트 15 〉	실패 (0.08ms, 16.3MB)
테스트 16 〉	실패 (0.10ms, 16MB)
테스트 17 〉	실패 (0.10ms, 16.5MB)
테스트 18 〉	실패 (0.17ms, 16.4MB)
테스트 19 〉	실패 (0.09ms, 16.5MB)
테스트 20 〉	실패 (0.09ms, 16.5MB)
테스트 21 〉	실패 (0.09ms, 16.3MB)
테스트 22 〉	실패 (0.08ms, 16.5MB)
테스트 23 〉	실패 (0.10ms, 16.4MB)
테스트 24 〉	실패 (0.09ms, 16.4MB)
테스트 25 〉	실패 (0.10ms, 16.5MB)

채점 결과

 

정답

코드

import Foundation
func solution(_ p:String) -> String {
    
    func modifyLogic(_ u: String, _ v: String) -> String {
        var sol = "("
        sol += v + ")"
        
        let firstIndex = u.index(after: u.startIndex)
        var temp = u[firstIndex...]
        temp.removeLast()
        
        for char in temp {
            if char == "(" {
                sol.append(")")
            } else {
                sol.append("(")
            }
        }
        
        return sol
    }
    
    func isRight(_ str: String) -> Bool {
        guard let first = str.first else {
            return true
        }
        
        if first == ")" {
            return false
        }
        
        return true
    }
    
    func recursion(_ str: String) -> String {
        var counter = 0
        var sol = ""
        var str = str
        
        for (n,i) in str.enumerated() {
//            print(counter, n, i, str)
            if i == "(" {
                counter += 1
            } else {
                counter -= 1
            }
            
            if counter == 0 {
                let index = str.index(str.startIndex, offsetBy: n)
                let nextIndex = str.index(after: index)
                var u = String(str[...index])
                var v = String(str[nextIndex...])
                
                let recursed = recursion(v)
                
//                print(u,v,recursed)
                
                if isRight(u) {
                    sol = u + recursed
                } else {
                    sol = modifyLogic(u, recursed)
                }
                
                break
            }
        }
        return sol
    }
    
    
    
    return recursion(p)
    
}

성능과 정확도

테스트 1 〉	통과 (0.07ms, 16.2MB)
테스트 2 〉	통과 (0.08ms, 16.2MB)
테스트 3 〉	통과 (0.06ms, 16MB)
테스트 4 〉	통과 (0.09ms, 16.4MB)
테스트 5 〉	통과 (0.10ms, 16.4MB)
테스트 6 〉	통과 (0.09ms, 16MB)
테스트 7 〉	통과 (0.10ms, 16.2MB)
테스트 8 〉	통과 (0.07ms, 16.2MB)
테스트 9 〉	통과 (0.09ms, 16.2MB)
테스트 10 〉	통과 (0.09ms, 16.4MB)
테스트 11 〉	통과 (0.11ms, 16.3MB)
테스트 12 〉	통과 (0.13ms, 16.5MB)
테스트 13 〉	통과 (0.14ms, 16.4MB)
테스트 14 〉	통과 (0.18ms, 16.4MB)
테스트 15 〉	통과 (0.21ms, 16.3MB)
테스트 16 〉	통과 (0.32ms, 16.2MB)
테스트 17 〉	통과 (0.39ms, 16.5MB)
테스트 18 〉	통과 (0.33ms, 16.4MB)
테스트 19 〉	통과 (0.55ms, 16.1MB)
테스트 20 〉	통과 (0.38ms, 16.2MB)
테스트 21 〉	통과 (0.42ms, 16.4MB)
테스트 22 〉	통과 (0.27ms, 16.4MB)
테스트 23 〉	통과 (0.40ms, 16.4MB)
테스트 24 〉	통과 (0.18ms, 16.3MB)
테스트 25 〉	통과 (0.22ms, 16.5MB)