[Swift Algorithm] 괄호 BOJ #9012

문제 설명

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

입출력 예제

입력

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

출력

NO
NO
YES
NO
YES
NO

 

내 문제 풀이

import Foundation

let count = Int(readLine()!)!

for _ in 0..<count {
    let input = readLine()!
    var stack = [Character]()
    var check = true
    
    for i in input {
        if i == "(" {
            stack.append(i)
        }
        else {
            if stack.isEmpty { check = false; break }
            else { stack.removeLast() }
        }
    }
    
    if check == false { print("NO") }
    else {
        if !stack.isEmpty { print("NO") }
        else { print("YES") }
    }
}

이 문제는 프로그래머스 올바른 괄호 문제와 아주 유사하다.

올바른 괄호 문제에서는 스택을 사용하지 않고 +, - 연산을 이용해 쉽게 풀었다.

하지만 여기서는 스택을 이용하여 다르게 풀이해보았다.

• "("가 입력되었는지, ")"가 입력되었는지를 기준으로 조건문을 작성했다.
• "("가 입력되었을 때는 후에 )가 올지, 아닐지 아직 모르는 상태이므로, stack에 추가만 해준다.
• ")" 입력시에는 이전에 맞는 "("쌍이 존재하는지를 체크해줘야한다. 
  이 때, 스택이 비었다면 옳지 않은 문장이 되므로 check를 false로 바꿔준 후 바로 break해준다.
  스택이 비어있지 않다면, 굳이 ")"는 추가해주지 않고,stack의 마지막 "("를 삭제해준다.
  ("("과 ")"이 알맞게 만났다면 올바른 쌍이기 때문에, 굳이 스택이 둘 필요없이 제거해준다.)
• 위와 같이 모든 괄호를 검사해준 뒤, check가 false로 바뀌어있다면 바로 "NO"를 출력하고,
  그렇지 않다면 스택이 비었는지를 확인해준다.
  스택이 비어있지않다면 올바른 쌍이 되지 못해 스택에 남은 괄호가 있다는 의미이므로,
  "NO"를 출력해주고, 그렇지 않다면 "YES"를 출력해준다.

 

💡 피드백

• 스택은 개념은 정말 쉽게 느껴지지만,
  막상 풀이할때는 복잡하고 생각보다 예외가 많아 푸는데 시간이 꽤 걸린다.
• 그래도 많이 풀다보니 점점 익숙해지고 있는 것 같아서,, 계속 복습해야겠다.

 

---

 

문제

https://www.acmicpc.net/problem/9012