스파르타 알고리즘 트랙 문제 4일차 - 3 #9012 괄호

문제

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

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

 

해결 과정

Stack의 가장 기본적인 활용인 괄호 문제이다. 입력에 "("이 들어오면 Stack에 저장해 두고, ")"이 들어오면 Stack에서 요소를 꺼내 비교한다. ")"이 들어왔는데 Stack이 비었거나, 문자열이 종료되었는데 Stack에 남아있는 요소가 있다면 VPS가 아닌 것이고, 그 외의 경우는 VPS이다.

 

import java.io.*; import java.util.*; import static java.lang.Integer.*; public class Main {     public static void main(String[] args) throws IOException {         BufferedReader a = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter b = new BufferedWriter(new OutputStreamWriter(System.out));         int N = parseInt(a.readLine());         Stack<String> arr = new Stack<>();         while (N!=0){             String ans = "YES";             String[] order = a.readLine().split("");             for (String s: order){                 if (s.equals("(")){                     arr.add(s);                 }                 else if (s.equals(")")){                     if(arr.size()==0){                         ans = "NO";                         break;                     }                     String tmp = arr.pop();                     if(!tmp.equals("(")){                         ans = "NO";                         break;                     }                 }             }             if(arr.size()!=0){                 ans = "NO";             }             b.write(ans+"\n");             arr.clear();             N--;         }         b.flush();         b.close();     } }

문자열을 전부 받은 다음, 위 과정을 동일하게 구현해 출력하는 코드를 작성하였다. Queue, Stack에 대한 문제는 어제부터 풀어 왔기 때문인지 과정과 코드를 막힘없이 생각하고 구현해 낼 수 있었다.