Swift) 프로그래머스(Lv2) - 괄호 변환 (Stack & Recursion)

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

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

안녕하세요. 후르륵짭짭 입니다.

이번에는 카카오블라인드 채용 문제를 다뤄보도록 하겠씁니다.

한 한시간 반 정도 걸린 것 같습니다.

이 문제는 스택으로 처음 풀었고요,,, 후에 다른 사람의 코드를 보고 재귀로 다시 풀었습니다.

 

** 스택으로 푼 풀이 **

func solution(_ p:String) -> String {
    
    let lists : [String] = Array(p).map({ (char) -> String in
        return String(char)
    })
    
    if lists.isEmpty{
        return ""
    }
    
    var answer = ""
    var tempStack = ""
    var braketCnt = 0
    var stack : [String] = []
    var pushStack : [String] = []
    
    for (index , element) in lists.enumerated() {
        
        if element == "("{
            braketCnt += 1
            stack.append(element)
        }
        else if element == ")"{
            braketCnt -= 1
            
            if !stack.isEmpty && stack.last == "("{
                stack.removeLast()
            }
        }
       
        tempStack.append(element)
        
        if braketCnt == 0 || index + 1 == lists.count{
            
            if stack.isEmpty && braketCnt == 0 {
                answer += tempStack
            }
            else{
                
                answer += "("
                
                var tempStackToString = tempStack.map { (char) -> String in
                    return String(char)
                }
                
                tempStackToString.removeFirst()
                tempStackToString.removeLast()
                
                for (index , element) in tempStackToString.enumerated() {
                    
                    if element == "(" {
                        tempStackToString[index] = ")"
                    }
                    else if element == ")"{
                        tempStackToString[index] = "("
                    }
                    
                }
                
                pushStack.insert(")"+tempStackToString.joined(), at: 0)
                
            }
            
            tempStack = ""
            stack = []
            
        }
        
    }
    
    print(answer)
    print(pushStack)

    return answer + pushStack.joined()
}

이 코드를 보면 모든 단어를 하나씩 확인을 해줍니다.

bracket은 괄호를 의미하는데 이게 동일하게 됐을 경우에 3단계 또는 4단계로 넘어 갑니다.

그전에 일단 스택과 원래 문자열을 담는 것을 사용해서 

균형잡힌 괄호 문자 일 때, 올바른 문자 인지 stack으로 확인 해줍니다. 

만약에 균형잡힌 문자이면서 올바른 문자라면 그냥 answer에 넣어줍니다.

반면 그게 아니라면 , 시작 부분에 "(" 를 넣어주고 pushStack에 ")" + 나머지를 뒤집은 문자 를 넣어줍니다.

그리고 마지막에 answer에 pushStack을 넣어주면 됩니다.

위와 같은 과정을 예시로 들자면

문자가 )( () ))(( 이렇게 되어 있을 때

1 . ")(" 균형잡혔지만 올바른 문자 아님 => answer += ( 그리고 pushStack = [")"]

2. () 균형잡히고 올바른 문자 => answer = "(" + "()" 그리고 pushStack = [")"]

3. ))(( 균형잡혔지만 올바른 문자 아님 => answer = "(" + "()" + "(" 그리고  pushStack = [")()"., ")"]

이렇게 돼서 answer = (()( + pushStack = [")()"., ")"] 을 더하면

정답인 (()()()) 이 된다.

 

** 재귀로 풀이 **

func solution2(_ p : String) -> String{
        
    return solve(p)
}

func solve(_ word : String) -> String{
    
    if word.isEmpty {
        return ""
    }
    
    var answer = ""
    
    let uvBlance = splitToUV(word)
    
    if uvBlance.blance {
        answer += uvBlance.u + solve(uvBlance.v)
    }
    else{
        answer += "("
        answer += solve(uvBlance.v)
        answer += ")"
        
        let startIndex = uvBlance.u.index(after: uvBlance.u.startIndex)
        let endIndex = uvBlance.v.index(before: uvBlance.u.endIndex)
        
        let middleWord = uvBlance.u[startIndex..<endIndex]
        
        for char in middleWord {
            
            if char == "("{
                answer += ")"
            }
            else if char == ")"{
                answer += "("
            }
            
        }
        
    }
    
    
    return answer
}

func splitToUV(_ word : String) -> (u : String, v : String, blance : Bool) {
    
    var blanceCnt : Int = 0
    var stack : [Character] = []
    var u : String = ""
    var v : String = ""
    for (index , element) in word.enumerated() {
        
        if element == "(" {
            blanceCnt += 1
            stack.append(element)
        }
        else if element == ")" {
            blanceCnt -= 1
            
            if !stack.isEmpty && stack.last == "(" {
                stack.removeLast()
            }
            
        }
        
        if blanceCnt == 0 {
            let splitIndex = word.index(word.startIndex, offsetBy: index + 1)
            u = String(word[word.startIndex..<splitIndex])
            v = String(word[splitIndex..<word.endIndex])
            break
        }
        
    }
    
    if stack.isEmpty {
        return (u,v,true)
    }
    
    return (u,v,false)
}

사실 상 위 과정은 동일하다!

하지만 여기서 알고 가면 좋을게 있다.

//after는 인덱스 바로 다음 위치
let startIndex = uvBlance.u.index(after: uvBlance.u.startIndex)
//before는 인덱스 바로 이전 위치
//endIndex는 문자의 마지막 부분을 의미 따라서 공백이 된다...
let endIndex = uvBlance.v.index(before: uvBlance.u.endIndex)

(참고로 endIndex는 "Hello"라고 할 때, "" 이렇게 공백의 위치가 된다...)

그리고 문자열을 배열로 변경 하지 않고 split 하기 위해서는 

//시작 index 부터 tempIndex 거리에 있는 index 위치 [0...tempIndex]
let splitIndex = word.index(word.startIndex, offsetBy: tempindex+1)
//이렇게 하면 range 값으로 배열로 변경하지 않고 String 형태로 추출 가능
let  u = String(word[word.startIndex..<splitIndex])
//endIndex는 마지막 공백을 의미한다. list.count의 위치
let  v = String(word[splitIndex..<word.endIndex])

이 정도만 알아두면 좋을 것 같다!!!

 

참고 사이트 :

www.appleofeyes.com/문자열-자르기-substring-swift-3-0/

스위프트에서 문자열 자르기 – substring / swift 3.0 | Revival