https://www.acmicpc.net/problem/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가 아니다.
다음은 자바로 구현한 풀이이다.
public class Stack_9012 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
int nowIndex = -1;
while( T-- > 0 ){
String PS = br.readLine();
for( int i = 0; i < PS.length(); i++ ){
if('(' == PS.charAt(i)){
nowIndex++;
if( nowIndex == -1 ) {nowIndex--; break;}
}
else
nowIndex--;
}
if( nowIndex == -1 )
sb.append("YES").append("\n");
else
sb.append("NO").append("\n");
nowIndex = -1;
}
System.out.println(sb);
}
}스택 자료구조는 사용하지 않고 int 변수를 사용하였다. 만약 '('가 확인된다면 인덱스를 하나씩 증가시켜주고 반대로 ')'가 확인된다면 인덱스를 하나씩 빼주는 식으로 풀이가 가능했다.
만약 입력이 )()이런 식으로 들어와도 if( nowIndex == -1 ) {nowIndex--; break;} 구문으로 예외 처리가 가능하다.
