▶ 문제
https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
▶ 설명
입력되는 문자가 열린괄호 ' ( ' 인지 닫힌괄호 ' ) ' 인지 체크하여서 열린괄호일 경우 Stack을 인스턴스한 변수에 쌓고, 닫힌 괄호일 경우 그 변수에서 들어있는 데이터를 빼도록 한다.
만일 데이터가 없는데 빼야한다면 EmptyStackException 이 발생할 수 있으므로 데이터가 없는지 확인한 후 예외 처리를 해줘야 하고, EmptyStrackException 이 발생할 것 같다면 그것은 문제에서 말하는 VPS 가 아니므로 괄호를 체크하던 작업을 멈추고, "NO"를 출력시켜야 한다.
▶ 문제 풀이
🌱 풀이1. Stack 자료구조 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
Stack<Character> bracket;
String s;
while (t > 0) {
bracket = new Stack<Character>();
s = br.readLine();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
bracket.push(s.charAt(i));
} else if (bracket.empty()) {
bracket.push(s.charAt(i));
break;
} else {
bracket.pop();
}
}
if (bracket.empty()) {
sb.append("YES").append("\n");
} else {
sb.append("NO").append("\n");
}
t--;
}
System.out.println(sb);
}
}Stack<Character> bracket;
괄호를 담을 공간을 미리 정해야 하는데, 이 때 String 이 아닌 Character 형 이라는 것에 주의한다.
for 문 안에는 3개의 if 가 있다.
그 중에서 두번째와 세번째 if 문을 눈여겨 봐야 하는데,
' ) ' 일 경우엔 바로 스택 저장공간에 들어있는 ' ( ' 를 빼내는 것이 아니라
비어있는지부터 확인해야 하므로 bracket.empty() 가 bracket.pop() 보다 앞선 if 문임을 유의하도록 한다.
만약 stack 공간 안이 비어있는 상태에 ' ) '가 입력값으로 들어온다면 올바르지 않은 VPS 이므로
반복문을 빠져나와 No를 출력하도록 해야 한다고 했다.
for반복문이 끝나면 stack 저장소에 데이터가 있는지 없는지를 체크하여
데이터가 하나도 없을 때 yes를, 데이터가 남겨져 있다면 no를 출력할 것이므로
입력값으로 들어온 문자를 stack 저장소에 집어넣고 반복문을 빠져나오도록 하면
내 의도대로 no가 출력된다. 그래서 break 전에 push 메소드를 사용하였다.
🌱 풀이2. Stack 외 방법
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
int result;
String s;
while (t > 0) {
result = 0;
s = br.readLine();
if (s.charAt(0) == '(' && s.charAt(s.length() - 1) == ')') {
result++;
for (int i = 1; i < s.length() - 1; i++) {
if (s.charAt(i) == '(') {
result += 1;
} else {
result -= 1;
}
if (result < 0) {
break;
}
}
result--;
if (result == 0) {
sb.append("YES").append("\n");
} else {
sb.append("NO").append("\n");
}
} else {
sb.append("NO").append("\n");
}
t--;
}
System.out.println(sb);
}
}
Stack 을 이용하지 않고 입력값에 따라 각각 +1, -1을 하도록 하는 간단한 코드로 작성해 보았다.
정상적인 VPS 라고 한다면 괄호가 쌍으로 이루어져 있으므로 결과적으로 0이 되어야 한다.
예를 들어 열린괄호 ' ( '가 3개 있으면 닫힌괄호 ' ) '도 3개여야만 한다. ' ( '가 올 때마다 +1를 해주고, ' ) '가 올 때마다 -1을 해주면 결과적으로 0이 나온다.
그리고 0보다 작거나 크다면 정상적인 괄호 쌍이라고 보지 않는 것이다.
for 문 안에 break 가 있는 이유는, 풀이1에서 stack 저장소가 비어있을 때 break 하는 것과 이유가 동일하다고 보면 된다.
()) 라는 입력값을 차례로 체크하고 있을 때 세번째 글자인 ) 가 올 때는 누적해서 연산한 값이 -1이다. 즉, 비정상적인 VPS 인 경우일 땐 0보다 작은 수임을 유추할 수 있으므로 음수일 경우 반복문을 멈추고 no를 출력하도록 하였다.
if (s.charAt(0) == '(' && s.charAt(s.length() - 1) == ')') { ... }
입력값이 어떤 괄호인지 체크하는 for 반복문이 오기 전에 열린괄호 ' ( '로 시작해야 하고 닫힌괄호 ' ) '로 문장이 끝나야 한다는 것을 전제로 하는 조건문을 만들었다. ' ) '로 시작하거나 ' ( '로 문장이 끝난다면 정상적인 VPS 로 보지 않기 때문이다.
▶ Log
Stack 을 활용하여 푸는 문제지만 왜인지 다른 방법으로 풀어보고 싶어서 +, - 연산을 이용하는 방법으로 먼저 문제에 접근해보았다. 하지만 내가 원하는 결과가 단번에 나오지 않아서 여러번 코드를 고쳐야 했고, 많은 조건을 달아야해서 생각지도 못하게 애를 먹은 거 같다. 이래서 Stack 을 쓰는구나 크게 체감했던 문제가 아니었나 싶다. 간단하게 Stack 메소드로 해결할 수 있음에 감사하다고 해야하나 모르겠다.
그나저나 책을 보니 Queue 보다도 Stack 이 먼저 나왔는데, 새롭게 자료구조를 카테고리화 하기 전에 나온 것이라서 다른 자료구조 Inteface와 다르게 Vector 에 속해 있다고 한다.
게다가 Interfae가 아닌 Class로 되어 있다고 하니 자바에서 터줏대감이기도 한 Stack 이 특별해 보인다.
