[백준] 괄호 (9012)(java)

원본 문제 : 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)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1

6

(())())

(((()())()

(()())((()))

((()()(()))(((())))()

()()()()(()()())()

(()((())()(

예제 출력 1

NO

NO

YES

NO

YES

NO

 

 

문제 풀이 1

처음 문제 풀이로 생각 난 것은 ArrayList에 각 '('와 ')'을 담아 두 사이즈가 같으면

"YES"를 출력, 다르면 "NO"로 출력하려고 했다.

예제 입력에 대한 출력이 올바르게 나왔지만, 채점 결과는 틀렸다고 한다.

이렇게 갯수를 카운트하면 틀릴 수가 없는데 왜 틀렸는지 모르겠다..

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = Integer.parseInt(sc.nextLine());
		
		String[] strArr = new String[N];
		for(int i = 0; i < N ; i++)
			strArr[i] = sc.nextLine();

		
		for(int i = 0; i < N ; i++) {
			ArrayList list1 = new ArrayList();
			ArrayList list2 = new ArrayList();
			for(int j = 0; j < strArr[i].length(); j++) {
				if(strArr[i].charAt(j)=='(')
					list1.add(strArr[i].charAt(j));
				else
					list2.add(strArr[i].charAt(j));
			}
			if(list1.size()==list2.size())
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
}

 

 

 

문제 풀이 2

문제의 의도대로 Stack을 이용해서 풀었다.

각 문자열을 탐색하면서 '('를 만나면 push를 하고, ')'를 만나면 pop하는 방법을 사용했다.

이럴 경우 예외가 발생하는데, Stack이 비어있는데 pop을 하면 에러가 발생한다.

이는 try - catch문으로 잡았으며

에러명을 정확히 몰라 뭉뚱그려 Exception으로 처리하였고,

문자열 처리가 다 '('가 ')'보다 많아서 Stack이 비어있지 않는 경우도 있으므로

이는 if와 else로 처리하였다.

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = Integer.parseInt(sc.nextLine());
		
		String[] strArr = new String[N];
		for(int i = 0; i < N ; i++)
			strArr[i] = sc.nextLine();

		
		for(int i = 0; i < N ; i++) {
			Stack stack = new Stack();
			try {
				for(int j = 0; j < strArr[i].length(); j++) {
					if(strArr[i].charAt(j)=='(')
						stack.push(strArr[i].charAt(j));
					else {
						stack.pop();
					}
				}
				if(stack.isEmpty())
					System.out.println("YES");
				else
					System.out.println("NO");
			} catch(Exception e) {
				System.out.println("NO");
			}
		}
	}
}