[백준/c++] 9012: 괄호

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

정답 코드

#include <iostream>
#include <stack>
using namespace std;
int main() {
	stack<char> st;
	int N;
	string s;
	cin >> N;
	for (int j = 0;j < N;j++) {
		cin >> s;
		bool succ = true;
		for (int i = 0;i < s.length();i++) {
			char ch = s.at(i);
			if (ch == '(') {
				st.push('(');
			}
			else {
				if (st.empty()) {
					succ = false;
					break;
				}
				else {
					st.pop();
				}
			}
		}
		if (succ && st.empty()) cout << "YES" << endl;
		else cout << "NO" << endl;
		// 스택 비우기
		while (!st.empty()) st.pop();
	}
	return 0;
}

스택을 사용하는 이유는?

')'에 해당하는 '('를 찾을 때 최근에 들어온 괄호를 기준으로 하기 때문이다
후입선출이므로 스택을 사용해야 한다

')' (오른쪽 괄호)를 스택에 넣지 않는 이유는?

'('와 짝이 맞는지만 확인하면 그 이후로는 사용되지 않기 때문이다

주의할 점

1. pop()을 하기 전에 스택이 비어있지 않은지를 미리 확인해야 한다

#include <iostream>
#include <stack>
using namespace std;
int main() {
	stack<char> st;
	int N;
	string s;
	cin >> N;
	for (int j = 0;j < N;j++) {
		cin >> s;
		bool succ = true;
		for (int i = 0;i < s.length();i++) {
			char ch = s.at(i);
			if (ch == '(') {
				st.push('(');
			}
			else {
				st.pop();
			}
		}
		if (succ && st.empty()) cout << "YES" << endl;
		else cout << "NO" << endl;
		// 스택 비우기
		while (!st.empty()) st.pop();
	}
	return 0;
}

이 코드처럼 st.empty()를 확인하지 않고 바로 st.pop()을 수행하면 에러가 발생한다

// 이렇게 입력하면 에러가 발생합니다
1
))

2. 괄호 문자열이 VPS인지 여러 테스트케이스를 확인하는 문제이다 따라서 한 테스트케이스의 실행이 끝나면 스택을 비워줘야 한다
스택은 clear()함수를 제공하지 않기 때문에 직접 반복문을 수행해서 스택을 비어있는 상태로 만들어야 한다 이 부분을 놓치면 다음 테스트케이스부터는 결과값이 완전히 달라질 수 있다

---

아래의 코드는 1년 전 자료구조를 배우지 않은 상태에서 파이썬을 구현한 코드이다 굳이 따지자면 로직은 같지만 자료구조를 활용해서 푼 지금의 코드가 메모리도 적게 사용하고 실행시간도 더 짧아 문제의 의도에 더 잘 접근한 것 같다 자료구조의 필요성이 체감된 순간이었다!

t=int(input())
for _ in range(t):
    n=input()
    A,B=0,0
    res=0
    for i in range(len(n)):
        if n[i]=='(':
            A+=1
        else:
            B+=1
        if B>A:
            res+=1
    if A==B:
        if res==0:
            print('YES')
        else:
            print('NO')
    else:
        print('NO')