[백준 BOJ][JAVA] 9012번: 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

저번에 스택 문제를 풀어봤는데, 이것도 비슷한 문제다!

그 전과 좀 다른 점은 저번에는 C언어에서 스택을 하나하나 구현해봤다면

이번엔 자바 Stack 클래스를 이용해서 푼다는 점!

 

사실 이 문제 읽고 약간 헉.. 했던 게 자료구조에서 스택 배울 때 주구장창 나왔던 예제가

딱 이 괄호 문제라 약간은 반갑고, 너 또 나오니..? 이런 심경이었다

한마디로 이 문제는 스택 복습하기 정말 좋은 문제라는 것!

 

 

문제 조건

 

 

문제 이해하기

 

먼저, 문제에서 나왔던 VPS에 대해 이해를 해보자. 

괄호 문자열(=VPS)는 두 개의 괄호 기호인 '('와 ')'로 구성되어 있는 문자열로, 그 중에서 괄호의 모양이 바르게 구성된 문자열이라고 한다.

'이게 뭔 소린가?' 할 수도 있지만, 한 마디로 문자열의 짝이 맞는 걸 VPS라고 생각하면 된다. 

위의 예시에서 첫번째는 VPS가 아니고, 두번째는 VPS다. 

이런 식으로, 문자열의 짝이 맞지 않으면 VPS인 것이다!

 

 

아이디어 도출하기

 

그렇다면, VPS가 아닌 걸 어떻게 밝혀내야 하는가?

이렇게 생각할 수도 있다.

문자열의 짝이 맞아야 하니까 '('의 개수와 ')'의 개수가 같으면 되는 것 아닌가?

 

아니면, 위의 그림에서 봤던 것처럼 ( ( ) ) ( ) ) 

왼쪽괄호와 오른쪽 괄호는 각각 짝이 있기 때문에 이 짝을 잘 찾아주면 되는 것 아닌가?

첫번째 예시에서 파란색 괄호만 덩그러니 남아서 VPS가 아닌 게 밝혀졌었으니까..

 

그러면 어떻게 해야 짝을 잘 찾아줄 수 있을까? 

여기서 스택의 개념을 적용해보면,

왼쪽 괄호를 push(), 오른쪽 괄호를 pop()이라고 생각해보자!

위의 예시를 보면, 스택에 파란색 오른쪽 괄호가 남아있는 것을 볼 수 있다!

얘는 VPS가 아닌 것이다..

 

 

위의 예시에서는 마지막에 스택이 비게 된다!

얘는 VPS인 것이다!

 

이런 식으로 왼쪽 괄호는 스택에 push를 해주고, 오른쪽 괄호는 pop을 해주면

사실 짝은 저절로 지어지며, 짝이 맞지 않는 경우 스택은 비워지지 않는다.

그래서, 스택이 비면 VPS, 안 비면 VPX(X)로 생각하면 된다.

 

우리는 수학에서 괄호를 배울 때, 가장 안쪽에 있는 괄호부터 계산을 하며, 안쪽부터 짝을 찾아준다고 배웠다.

그걸 생각해보면  ( ( ) ) 이런 식으로 괄호가 있을 때, 

왼쪽 괄호가 쭉 있다가 오른쪽 괄호가 나왔을 때, LIFO(Last In First Out)

가장 나중에 나온 왼쪽 괄호가 가장 먼저 짝을 찾아 탈출한다고 생각해볼 수도 있다.

 

그리고 이해하기 쉽도록 괄호를 색깔별로, 짝을 맞춰서 해봤지만

사실 색깔 없이도 스택 개념을 활용하면 괄호의 짝을 바로 찾아줄 수 있다.

 

 

그리고 이러한 개념은 소괄호()뿐만 아니라, 중괄호{}, 대괄호[]를 사용한 예시가 있다면 더 쉽게 이해할 수 있다.

한번 해보자!

스택을 활용해서 소괄호와 중괄호, 대괄호의 짝을 찾아 push, pop하는 것을 볼 수 있다!

 

이 예시를 더 활용하면, 소괄호, 중괄호, 대괄호의 수식이 틀리지 않았는지 판별할 수도 있다.

근데 이 괄호 문제와는 거리가 점점 멀어지는 것 같으니 이건 다음 포스팅 때 해보자!

(+ 백준에 이 문제와 비슷한 게 분명 있을 것 같아서 찾아봤는데.. 역시나 있다

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

이건 다음 포스팅 때 해보는 걸로!)

 

어쨌든 이런 식으로, 스택의 개념을 이용하면 이 문제를 쉽게 풀 수 있을 것이다!

이제 코드를 짜보자!

 

 

문제 풀이 (코드)

 

1. 왼쪽 괄호가 입력되면, push

 

2. 오른쪽 괄호가 입력되면, pop

 

3. 스택이 비어있을 때, 오른쪽 괄호가 입력되면 VPS (X)

-> 스택이 이미 비어있는데, 오른쪽 괄호가 입력된거면 소괄호 짝이 안 맞은 것.

-> 스택이 비어있다는 건, 앞에서 왼쪽 괄호가 나오지 않았거나, 이미 짝을 다 이룬 것이기 때문..

-> 근데, 거기서 오른쪽 괄호 입력? 소괄호 짝이 안 맞았다!

-> break문으로 빠져나와 "NO" 출력

 

4. 만약, 최종결과에서 스택이 비어있으면 VPS (O) -> "YES" 출력

비어있지 않으면, VPS (X) -> "NO" 출력

 

5. 한 괄호 문자열을 판별하고 나면, 스택 비워두기

-> 다음 괄호 문자열을 판별하기 위해!

-> .clear() 이용

 

 

밑의 코드는 위의 생각을 바탕으로 코드를 짜본 결과이다.

(사실 코드 다 짜고 나서, 런타임 오류나서 3번 내용의 코드를 추가했다..)

// 백준 9012번: 괄호 (스택 문제)
import java.util.Scanner;
import java.util.Stack;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		Stack<String> stack = new Stack<>(); // char형 스택 선언
		
		int n = scan.nextInt(); // 입력받을 괄호 문자열의 개수 n 입력
		for (int i = 0; i < n; i++) {
			String str = scan.next(); // 괄호 문자열 입력
			int j;
			for (j = 0; j < str.length(); j++) {
				String bracket = String.valueOf(str.charAt(j)); // str[j]를 가져온 것 (str 문자열의 j번째 인덱스에 있는 값 가져오고, 그 값(char)을 String으로 변환)
				if (bracket.equals("(")) { // 소괄호가 "("일 때,
					stack.push(bracket);
				} else { // 소괄호가 ")"일 때
					if (!stack.empty()) { // 스택이 이미 비어있는 상태에서 pop()을 하면 에러남
						stack.pop();
					} else { // 스택이 empty인데 pop()을 한다는 건 소괄호의 짝이 맞지 않았다는 것.
						break;
					}
				}
			}
			if (stack.empty() && j == str.length()) { // j가 str의 length와 다르다는 건 중간에 break가 있었다는 것 -> 소괄호의 짝 안 맞음
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
			stack.clear(); // 스택을 비워야 다음 괄호 문자열 제대로 판별 가능
		}
		scan.close();
	}

}

 

이렇게 얼렁뚱땅 스택을 활용하여 백준 괄호 문제를 풀어보았고,

생각보다 코드가 깔끔하지 않아서 좀 아쉽다..

(왜 자바는 1차원 문자형 배열에서 str[index]가 안 되는 거냐!!!)

더 코드를 깔끔하게 짤 수 있도록 고민을 해보자..

 

그래도 오랜만에 스택 그림 그려가면서 복습을 해보니까

나름 즐거웠던 것 같다.!

다음엔 아까 언급했던 백준 4949번: 균형잡힌 세상을 풀어보는 걸로~

 

 

그리고 혹시 이 글을 보시는 분들 중,

제가 틀린 부분이 있다면 언제든지 피드백 부탁드립니다 :)