[프로그래머스] 괄호 회전하기

 

▼ 문제 링크

코딩테스트 연습 - 괄호 회전하기

 

괄호를 회전한다는게 당최 무슨 말인지...? 했는데 알고보니까 회전... 이라기 보다는 한 칸씩 앞으로 민다는 말이 더 맞는 것 같다. 문제에서 주어진 예제를 살펴보자.

왼쪽으로 '회전'이란 말 대신, 왼쪽으로 '한 칸씩 이동'이라고 생각하면 쉽다.
아래 그림처럼 맨 앞의 괄호가 밀려서 맨 뒤로 이동하는 것이다. 

이렇게 괄호를 이동시키는 과정을 괄호의 개수-1만큼 반복한다.

이 문제를 해결하기 위해 일단 첫번째로 주어진 괄호가 개폐가 옳은 괄호인지 아닌지 확인하고, 두번째로 이 괄호들은 한 칸씩 이동해 새로운 괄호열을 만든다. 그리고 그 괄호열을 다시 첫번째 과정인 옳은 괄호인지 확인하는 절차를 밟으면 된다.

 

1단계: 옳은 괄호인지 확인하기

private func isCorrect(_ brackets: [String]) -> Bool {
    var stack: [Int] = []
    
    func bracketToNumber(_ bracket: String) -> Int {
        var number = 0
        
        switch bracket {
            case "(": number = 1
            case "{": number = 2
            case "[": number = 3
            case ")": number = -1
            case "}": number = -2
            case "]": number = -3
            default: number = 0
        }
        
        return number
    }
    
    // (: 1, {: 2, [: 3, ): -1, }: -2, ]: -3
    for bracket in brackets {
        let target = bracketToNumber(bracket)
        
        if let last = stack.last {
            if last > 0 && last + target == 0 {
                stack.removeLast()
            } else {
                stack.append(target)
            }
        } else {
            stack.append(target)
        }
    }
    
    return stack.isEmpty
}

개폐가 옳은 괄호인지 확인하기 위해 문자열인 괄호를 숫자로 변환한다.
열린 괄호는 양수로, 닫힌 괄호는 음수로 설정해뒀다. (: 1, {: 2, [: 3, ): -1, }: -2, ]: -3

후입선출 구조인 stack을 생각하며 배열에 숫자를 하나씩 배열에 추가한다.

이때 배열의 마지막 요소와 추가될 요소의 합이 0이 되면 두 개의 요소가 쌍을 이루는 것을 알 수 있다.
단, 이때 )( 인 경우에는 두 요소의 합이 0이어도 개폐가 옳지 않으므로 먼저 입력된 괄호가 양수(열린 괄호)여야 한다는 조건을 추가해줘야한다.

두 요소가 올바른 쌍을 이루고 있다면 배열에 추가하지 않고 두 요소를 모두 제거한다.
마지막에 stack 배열에 아무것도 남지 않았다면 옳은 개폐이고, 남아있는 괄호가 있다면 옳지 않은 개폐이다.

 

2단계: 괄호를 왼쪽으로 한 칸씩 이동시키기

func solution(_ s: String) -> Int {
    var brackets: [String] = []
    
    s.forEach({ brackets.append(String($0)) })
    
    var result = (isCorrect(brackets) ? 1 : 0)
    
    for _ in 1..<brackets.count {
        let first = brackets.removeFirst()
        brackets.append(first)
        result += (isCorrect(brackets) ? 1 : 0)
    }
    
    return result
}

배열의 첫번째 요소를 빼서 배열의 마지막에 추가한다.
바꾼 배열이 개폐가 옳은 배열인지 확인하고 맞다면 횟수를 1씩 추가해주면 된다.

 

전체 코드

import Foundation

func solution(_ s: String) -> Int {
    var brackets: [String] = []
    
    s.forEach({ brackets.append(String($0)) })
    
    var result = (isCorrect(brackets) ? 1 : 0)
    
    for _ in 1..<brackets.count {
        let first = brackets.removeFirst()
        brackets.append(first)
        result += (isCorrect(brackets) ? 1 : 0)
    }
    
    return result
}

private func isCorrect(_ brackets: [String]) -> Bool {
    var stack: [Int] = []
    
    func bracketToNumber(_ bracket: String) -> Int {
        var number = 0
        
        switch bracket {
            case "(": number = 1
            case "{": number = 2
            case "[": number = 3
            case ")": number = -1
            case "}": number = -2
            case "]": number = -3
            default: number = 0
        }
        
        return number
    }
    
    // (: 1, {: 2, [: 3, ): -1, }: -2, ]: -3
    for bracket in brackets {
        let target = bracketToNumber(bracket)
        
        if let last = stack.last {
            if last > 0 && last + target == 0 {
                stack.removeLast()
            } else {
                stack.append(target)
            }
        } else {
            stack.append(target)
        }
    }
    
    return stack.isEmpty
}