[백준] 9012번 : 괄호

Darak·2022년 1월 23일

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 이하이다.

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

출력

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

NO
NO
YES
NO
YES
NO

풀이

Ver. 1

먼저 대략적인 틀을 잡아야 하는데, 일단 주어진 개수만큼의 괄호 문자열을 입력받을 수 있도록 했다. 지금 정리하면서 보니까 저 부분을 함수로 짰어도 괜찮았을 것 같은데, 첫 시도에 내가 어떻게 접근했는지를 기록하는 거니까 그냥 그대로 써 보도록 하겠다.

int n = sc.nextInt();
String str[] = new String[n];
		
for (int i = 0; i < n; i++){
	String s = sc.next();
    
	//(VPS 여부를 판별하는 코드)
    
}

이제 VPS여부를 판별하는 코드 부분만 작성하면 문제를 풀 수 있다. VPS란 결국 괄호 문자열에서 '(' 다음에 반드시 ')'가 오는 것이 보장되어 있는 괄호 문자열이라고 할 수 있다.
이를 판별하기 위해서 스택을 이용했는데, 먼저 각 문자열을 문자 단위로 쪼갠 후 스택에 '(' 가 있으면 ')' 일 때 pop()을 이용해 스택에 있던 '(' 를 빼는 식으로 알고리즘을 구현하였다.

for (int j = 0; j < s.length(); j++) {
	char c = s.charAt(j);
	if (stack.peek() == '(' && c == ')')
		stack.pop();
	else
		stack.push();
}

그러나 이렇게 하면 스택에 '(' 가 있는지 확인하는 과정에서 스택이 비어 있으면 오류가 생기는데, 이를 위해 앞부분에 스택이 비어 있다면 무조건 넣는 코드를 추가하였다.

if (stack.isEmpty())
	stack.push();

마지막으로 VPS를 판별하기만 하면 된다. VPS는 '(' 와 ')' 가 동일한 개수를 가지고 있고 한 '(' 는 다른 ')' 와 순서대로 짝을 이루므로, 어떤 문자열이 VPS라면 각 문자에 대해 위의 연산을 모두 끝낸 후에 스택이 비어 있을 것이다. '(' 가 입력된 만큼 ')' 도 입력되기 때문이다.

따라서 스택이 비어 있다면 YES를, 아니라면 NO를 출력하도록 하였다. 다만 입력이 모두 끝난 후 한번에 출력해야 하니 따로 출력용 문자열 배열에 넣어서 이를 구현하였다.

if (stack.isEmpty())
	str[i] == "YES";
else
	str[i] == "NO";

Ver. 1 전체 코드

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

public class BJ_9012 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Character> stack = new Stack<>();
		
		int n = sc.nextInt();
		String str[] = new String[n];
		
		for (int i = 0; i < n; i++){
			String s = sc.next();
			for (int j = 0; j < s.length(); j++){
				char c = s.charAt(j);
				if (stack.isEmpty())
					stack.push(c);
				else if (stack.peek() == '(' && c == ')')
					stack.pop();
				else
					stack.push(c);
			}
            
			if (stack.isEmpty())
				str[i] = "YES";
			else
				str[i] = "NO";
			stack.clear();
		}
		
		for (String s : str)
			System.out.println(s);
	}
    
}

문자열을 입력받을 때에는 반드시 sc.next()를 사용해야 한다. sc.nextLine()을 사용했더니 입력 버퍼에 \n이 남아서 실행 결과가 이상해졌기 때문이다.
여기서는 String으로 입력받고 charAt()메소드를 이용했지만, 입력 자체를 char[]에 해도 괜찮았을 것 같기도 하고...
또 stack.clear()를 앞에서 하는 게 나았을 것 같기도 하다. 스택을 새롭게 초기화한다는 의미로.

Ver. 2

이렇게 풀고 결과는 맞았지만 영 찜찜한 기분이 들었다. 무엇보다 push()가 중복해서 두번이나 써진다는 것이 마음에 안들었다.
그래서 다른 사람들은 어떻게 하나 봤더니 flag변수(~인지 아닌지)를 이용해서 VPS여부를 판단하는 식으로 알고리즘을 구현해서 나도 그 방법을 적용해 보기로 했다.

일단 기존 알고리즘이 영 마음에 안들고 구린 부분이 있어서 명확하게 하기 위해 경우별로 나누어서 생각해 보기로 했다.
먼저 입력은 '(' 아니면 ')' 둘 중에 하나이고, 스택의 상태도 비었거나 비지 않았거나 둘 중 하나이므로 각각의 경우에 대해 대략적으로 의사 코드를 작성해 보았다.

if (스택이 비었으면)
	if ('(')
		stack.push();
	else if (')')
		isVPS = false;
	//'(' 가 나오고 ')' 가 나와야 하는데 먼저 ')' 가 나와버린 경우
	//어떻게 해도 짝이 맞지 않기 때문에 뒤를 볼 필요 없이 VPS가 아님
    
else //스택이 비어 있지 않으면
	if ('(')
		stack.push();
	else if (')')
		stack.pop();
	//스택에는 반드시 '(' 만 들어가므로
	//스택이 비어 있지 않다면 ')' 에 대응하는 '(' 가 반드시 존재

이를 통해 '(' 일 때에는 스택이 비어있는지에 관계없이 반드시 push()를 함을 알 수 있었다.
그 외에도 처음부터 ')' 가 입력되면 뒤를 볼 필요 없이 VPS가 아님을 판단할 수 있다는 것도 새롭게 알았다. 이래서 다른 사람들의 코드를 같이 보면서 공부해야 하는 거구나 싶었다.

아무튼 이를 토대로 VPS를 판별하는 코드를 다시 작성하였다.

boolean isVPS = true;
for (int j = 0; j < s.length(); j++){
	char c = s.charAt(j);
	if (c == '(')
		stack.push(c);
	else if (!stack.isEmpty())
		stack.pop();
	else {
		isVPS = false;
		break;
	}
}
if(!stack.isEmpty())
	isVPS = false;

Ver. 2 전체 코드

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

public class BJ_9012 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Character> stack = new Stack<>();
		
		int n = sc.nextInt();
		String str[] = new String[n];
		
		for (int i = 0; i < n; i++){
			String s = sc.next();
			boolean isVPS = true;
			for (int j = 0; j < s.length(); j++){
				char c = s.charAt(j);
				if (c == '(')
					stack.push(c);
				else if (!stack.isEmpty())
					stack.pop();
				else {
					isVPS = false;
					break;	
				}
			}
			if (!stack.isEmpty())
				isVPS = false;
            
			if(isVPS)
				str[i] = "YES";
			else
				str[i] = "NO";
			stack.clear();
		}
		
		for (String s : str)
			System.out.println(s);
	}
    
}