BOJ 9012 - 괄호

괄호 - 🥈 Silver 4

• 문제 링크
  https://www.acmicpc.net/problem/9012

stack으로 풀이할 수 있는 문제이다. 괄호로 이루어진 문자열을 처음부터 탐색하며 아래의 경우에 따라 다르게 처리해준다.

• 열린 괄호인 경우 : (
  -> stack에 열린 괄호 push
• 닫힌 괄호일 경우 : )
  -> stack의 top이 (이면 pop
  -> stack이 비어있으면 VPS가 아님
• 끝까지 탐색을 완료한 경우
  -> stack이 비어있으면 VPS
  -> stack이 비어있지 않으면 VPS가 아님

풀이 코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
	int n{ 0 };
	cin >> n;

	for (int i = 0; i < n; i++) {
		// 입력받을 문자열 선언
		string input;
		cin >> input;

		// 문자열을 탐색하며 사용할 stack 선언
		stack<char> s;

		// VPS인지 판단할 result 변수 선언 + 초기화
		int result = 1;

		// 문자열을 처음부터 끝까지 탐색
		for (int j = 0; j < input.length(); j++) {
			// 열린 괄호일 경우 push
			if (input[j] == '(') {
				s.push(input[j]);
			}
			// 닫힌 괄호일 경우
			else if (input[j] == ')') {
				// 비어있다면 VPS가 아니므로 result를 -1로
				if (s.empty()) {
					result = -1;
					break;
				}
				// 비어있지 않다면 pop
				else if (s.top() == '(') {
					s.pop();
				}
			}
		}

		// 탐색 종료 이후 stack이 비어있지 않다면 result를 -1로
		if (!s.empty()) {
			result = -1;
		}

		// result가 1이라면 YES, -1이라면 NO 출력
		if (result == 1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}

	// 프로그램 종료
	return 0;
}

결과