[백준 BOJ] 9012번 괄호 (C++/cpp)

문제 설명

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

9012번: 괄호

 

접근 방법 - 스택을 이용한 참/거짓 판별 문제

백준의 9012번 문제는 스택을 이용하여 정답을 구해야 하는 문제이다.

해당 문제에선, 주어지는 문자열에 대해 괄호가 각각 올바르게 짝지어져 있는지에 대한 여부를 묻고 있다.

필자는 해당 문제를 해결할 때, ( 를 만나면 스택에 push, ) 를 만나면 스택의 top값을 pop 하도록 하였다.

다만 특수한 경우에선 예외적인 연산을 주기도 하였다. 이에 관한 자세한 설명은 아래에서 하고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(n)를 입력받는다.

 

2) 스택(s)을 선언하고, 문자열(str)을 하나씩 입력받는다.

 

3) 반복문을 실행하여 아래 연산을 수행한다.

- ( 문자가 탐색되면, 스택에 1을 push 한다.

- ) 문자가 탐색되면, 스택이 비어있는지 확인한다.

스택에 무언가 있다면 top값을 pop 하고, 비어있다면 스택에 1을 push 한 뒤 해당 반복문을 탈출한다.

(최종적으로 스택이 비어있을 시에 "YES"를 출력하게끔 할 것이다. 따라서, 후자의 경우는 짝이 맞지 않아 "NO"를 출력해야 하기 때문에 pop이 아닌 push 연산을 해야 한다.)

 

4) 스택이 비어있는지 확인한다.

비어있다면 "YES"를 출력하고, 무언가 있다면 "NO"를 출력한다.

 

5) 모든 테스트 케이스가 2) ~ 4) 과정을 끝냈다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <stack>
#include <string>
using namespace std;

//백준 9012번 코드
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		stack<int> s;
		string str;
		cin >> str;	//미리 문자열 전체 입력받기
		for (int j = 0; j < str.length(); j++) {
			if (str[j] == '(') { s.push(1); }	// ( 글자 만나면 푸쉬
			else {
				if (!s.empty()) { s.pop(); }	// 1이 있을 때 ) 만나면 팝
				else {
					s.push(1);
					break;	// 비어있을 때 ) 만나면 푸쉬 후 스택 작업 끝내기
							// (어차피 NO 출력하게끔)
				}
			}
		}
		if (s.empty()) { cout << "YES\n"; }	// 비어있으면 YES
		else{ cout << "NO\n"; }		// 비어있지 않으면 NO
	}
}

 

제출 결과

(2022.01.01 백준 9012번 문제 제출 결과)