BRACKETS2(짝이맞지않는괄호)

(출처) https://algospot.com/judge/problem/read/BRACKETS2

여는 괄호와 닫는 괄호

해당 문제는 여는 괄호와 닫는 괄호가 쌍을 제대로 이루고 있는지 주어진 조건대로 판단을 해야 하는 문제이다. 괄호패턴을 직접 그려 나가다 보면 판단이 되는 기준은 결국 닫는 괄호가 된다는 것을 생각보다 쉽게 알 수 있다.

괄호패턴을 몇 개 직접 그려본다면, 문제의 조건에 부합하는 괄호패턴들은 어떤 것이든 모두 가장 첫 번째로 나오는 닫는괄호의 바로 앞에 해당 괄호와 쌍을 이루는 여는 괄호가 반드시 존재하고 있다는 사실을 발견할 수 있다. 그리고 이렇게 짝을 맞춘 괄호를 패턴에서 삭제하고 다시 다음번으로 가장 빠른 닫는괄호를 바라봤을 때도 위의 사실이 똑같이 성립한다는 것 또한 알 수 있다.

즉 가장 빠른 닫는 괄호를 기준으로 바로 앞자리의 괄호가 쌍이 맞는 여는 괄호인지를 판단해가며 모든 쌍이 제대로 맞는지 전부 확인하면 되는 문제이다.

앞에서부터 하나씩 괄호를 저장해 간다고 했을 때, 최초로 등장하는 닫는 괄호는 가장 마지막에 저장된 여는 괄호와 함께 짝을 지어서 삭제되게끔 구현되어야 한다. 따라서 구현에 이용할 특정 자료구조를 굳이 뽑아보자면 스택을 이용하는 것이 제일 편해 보였다. 벡터로도 충분히 구현이 가능해 보였지만 스택 자료구조를 이용하라고 대놓고 유도하고 있는 문제 같아서 스택으로 구현해 보았음.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>

using namespace std;
stack<char> brackets2(string& pattern) {
	stack<char> s;
	for (int i = 0; i < pattern.size(); i++) {
		if (pattern[i] == '(' || pattern[i] == '{' || pattern[i] == '[') s.push(pattern[i]);
		else {
			if (pattern[i] == ')') {
				if (s.empty() || s.top() != '(') {
					s.push('N');
					break;
				}
				else {
					s.pop();
					continue;
				}
			}
			if (pattern[i] == '}') {
				if (s.empty() || s.top() != '{') {
					s.push('N');
				}
				else {
					s.pop();
					continue;
				}
			}
			if (pattern[i] == ']') {
				if (s.empty() || s.top() != '[') {
					s.push('N');
				}
				else {
					s.pop();
					continue;
				}
			}
		}
	}
	return s;
}

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

	int testcase;
	cin >> testcase;
	while (testcase--) {
		string pattern;
		cin >> pattern;
		stack<char> ret = brackets2(pattern);
		if (ret.size() != 0) cout << "NO" << '\n';
		else cout << "YES" << '\n';
	}
	return 0;
}

기억하고 싶은 점

책에서 구현한 코드를 보면 여는괄호와 닫는괄호의 문자 목록을 2개의 배열에 따로 저장해놓고, 서로 쌍을 이루는 괄호들은 각 배열의 같은 인덱스를 사용하게끔 하여 논리적인 쌍을 이루어 놓았다. 진짜 책의 구현과 내 구현을 비교해보면 내 구현은 엄청 초라해 보이더라. 이런 식으로 코드를 짜는 법은 꼭 익혀두고 싶다.