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

난이도 : Lv 2

분류 : 스택

 

문제

 

프로그래머스

 

 

코드

 

import Foundation

func solution(_ s:String) -> Int {
    let n = s.count
    let s = Array(s)
    var answer = 0
    
    for i in 0..<n { // 문자열을 회전시키는 모든 경우만큼 반복
        var stack = [Character]()
        
        var is_valid = true // 괄호 문자열이 올바른지 확인할 변수
        
        for j in 0..<n { // 회전한 문자열 순회, 문자열 검사
        
            let c = s[(i+j)%n] // 회전한 문자열 인덱스 계산
            
            if c == "(" || c == "[" || c == "{" { // 여는 괄호일 경우
                stack.append(c) // 스택에 추가
                
            } else { // 닫는 괄호일 경우
                if stack.isEmpty { // 스택이 비어 있을 경우 괄호가 올바르지 않음
                    is_valid = false
                    break
                }
                let top = stack.last! // 스택의 top을 가져옵니다.
                
                if (c == ")" && top == "(") || (c == "]" && top == "[") || (c == "}" && top == "{") { // 매치되는 경우 스택에서 top을 제거합니다.
                    stack.removeLast()
                    
                } else { // 매치되지 않는 경우 괄호가 올바르지 않음
                    is_valid = false
                    break
                }
            }
        }
        if stack.isEmpty && is_valid { // 스택이 비어 있고, 괄호가 올바를 경우 1 추가
            answer += 1
        }
    }
    
    return answer
}

 

풀이

1. 문자열을 배열로 만들어서 인덱스로만 회전을 가한다.

2. 인덱스로 회전시킨 문자열의 0번째 글자부터 괄호를 확인한다. 이 때, 스택이 비어있는데 괄호가 닫힌다면 빠져나온다.

3. 열려있는 괄호를 스택에 쌓았다면 나머지 글자를 확인해서 스택의 Top 부분과 매칭시킨다.

4. 스택이 비어있고 is_valid 가 true 라면 올바른 문자열 개수를 늘린다.

 

P.S

인덱스로 회전을 시키는 방법이 참 좋은 것 같습니다.

기존의 코드는 removeLast, insert 를 사용해서 오버헤드가 발생했는데,

인덱스를 사용하니 오버헤드 없이 깔끔하고 빠르게 풀이가 가능합니다.