[Swift] 백준 9012번 - 괄호

백준 문제 모음

문제 링크

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

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”를 한 줄에 하나씩 차례대로 출력해야 한다. 

입출력 예시

알고리즘 분류

• 자료 구조
• 문자열
• 스택

---

문제 풀이

• 정수 T를 입력받아 T만큼 반복한다.
• input에 입력받은 문자열을 입력받고, stack은 Character형 배열로 초기화한다. flag도 true로 초기화한다.
• input의 요소를 순서대로 꺼내 s에 대입하고, for문의 구문을 실행한다.
  • 입력받은 문자열에서 "(" 이면 stack에 추가한다.
  • ")"인 경우, stack이 비어있으면 flag를 false로 바꾼 후 for문을 종료한다. 비어있지 않다면 stack의 마지막 요소를 삭제한다.
  • for문이 종료되고, stack이 비어있고 flag가 true라면 "Yes"를, 아니라면 "No"를 출력한다.

소스코드

for _ in 0..<Int(readLine()!)! {
    let input = readLine()!
    var stack = [Character]()
    var flag = true

    for s in input{
        if s == "(" {
            stack.append("(")
        }
        else {
            if stack.isEmpty {
                flag = false
                break
            }
            stack.removeLast()
        }
    }
    stack.isEmpty && flag ? print("YES") : print("NO")
}

• 8ms 소요

다른 코드

func isValidPS(_ str: String) -> Bool {
    var standard = 0
    for char in str {
        if char == "(" {
            standard += 1
        } else if char == ")" {
            standard -= 1
        }
           
        if standard < 0 {
            return false
        }
    }
    return standard == 0
}

if let inputNumber = Int(readLine() ?? "") {
    for _ in 0..<inputNumber {
        print(isValidPS(readLine() ?? "") ? "YES" : "NO")
    }
}

• "(" 일 때 변수 standard에 1을 더하고, ")"일 때 1을 뺀다.
• standard가 0보다 작아지면 false를 반환한다.
• 8ms 소요