Treejin's Note

문제 설명

• 둥근 괄호는 (로 열고 ) 로 닫는다.
• 중괄호는 {로 열고}로 닫는다.
• 대괄호는 [로 열고 ]로 닫는다.
• 모든 괄호쌍은 먼저 열린 뒤 닫힌다.
• 한 괄호쌍이 다른 괄호쌍과 서로 '교차해' 있으면 안된다.
• 문자열의 길이는 1 이상 10,000이하이다.

=> 괄호 문자열이 짝이 맞으면 'YES'를, 안맞으면 'NO'를 출력한다.

문제 풀이

괄호 짝 찾기

괄호쌍이 완성되려면 여는 괄호 후 닫는 괄호가 존재해야 한다.

또한 여는 괄호와 닫는 괄호 사이에 미완성인 괄호가 있어도 안된다.

스택을 이용하면 괄호의 짝을 쉽게 저장할 수 있다.(나는 STL을 쓰는 대신에 배열을 스택처럼 활용했다.)

여는 괄호가 나오면 스택에 저장하고,

닫는 괄호가 나오면 바로 이전에 짝인 괄호가 스택에 저장되어 있는지 확인한다.

이전에 짝인 괄호가 있는 경우엔 완성된 괄호쌍이므로 여는 괄호까지 스택에서 제거해주고,

이전에 짝인 괄호가 없다면 이는 미완성된 괄호쌍이므로 NO를 출력한다.

끝까지 완성된 문자열인지 확인하기

위의 방식대로 하면 괄호의 짝은 찾을 수 있지만, 닫는 괄호에서 연산 동작을 수행하기 때문에 여는 괄호로 끝나는 문자열은 올바른 괄호쌍으로 이루어져 있는지 확인할 수 없다.

따라서 최종적으로 스택에 남아있는 괄호가 없어야 끝까지 완성된 문자열이라는 것이 확인된다.

스택이 비었는지 확인해주자.

문제 풀이 코드

#include <iostream>

#define MAXVALUE 10010

using namespace std;

char charArr[MAXVALUE];
char stack[MAXVALUE];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int C;
	cin >> C;
	cin.getline(charArr, 1);	// 한 줄을 안읽는듯?
	for (int tc = 1; tc <= C; ++tc) {
		cin.getline(charArr, MAXVALUE);
		int top = 0;
		bool flag = true;
		int index = 0;
		while (flag && charArr[index] != '\0') {
			switch(charArr[index]) {
			case '(':
			case '{':
			case '[':
				stack[top++] = charArr[index];
				break;
			case ')':
				if (top > 0 && stack[top - 1] == '(') {
					--top;
				}
				else {
					flag = false;
				}
				break;
			case '}':
				if (top > 0 && stack[top - 1] == '{') {
					--top;
				}
				else {
					flag = false;
				}
				break;
			case ']':
				if (top > 0 && stack[top - 1] == '[') {
					--top;
				}
				else {
					flag = false;
				}
				break;
			
			}
			++index;
		}
		if (flag && top == 0)	// 괄호쌍이 전부 닫히면 top == 0
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}