[백준/C++] 9012번 괄호

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

9012번: 괄호

 

 

문제 분석

여는 괄호와 닫는 괄호로 이루어진 문자열이 주어지고,

주어진 괄호들의 쌍이 올바른지 확인하는 문제이다.

입력으로는 표준입력을 사용하며, T개의 테스트 데이터로 주어진다. 입력의 첫번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어지고, 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력으로는 표준 출력을 사용하며, 만일 입력 괄호 문자열이 올바른 괄호 문자열이면 "YES", 아니면 "NO"를 한 줄에 하나씩 차례대로 출력해야한다.

여기서 떠올릴 수 있는 해결법은 스택을 이용한 방법이 있다.

먼저, 입력받은 문자열을 탐색하여 여는 괄호를 만났을 경우, 스택에 PUSH하고 닫는 괄호를 만났을 경우, POP을 해주어 문자열의 괄호들이 알맞게 짝을 지어졌는지 판단할 수 있다.

코드

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


int main() {
	int cnt = 0;
	int flag = 0; // true/false 판단을 위한 flag
	string str;

	cin >> cnt;
	for (int i = 0; i < cnt; i++) {
		stack<char> s; // 스택선언
		cin >> str;
		for (int j = 0; j < str.size(); j++) {
			if (str[j] == '(') {
				s.push(str[j]); // 여는 괄호를 만나면 push
			}
			else if (str[j] == ')') { // 닫는 괄호를 만났을 때
				if (s.empty()) { // 스택이 비어있다면 오류이므로 flag를 1로 세워주고 break
					flag = 1;
					break;
				}
				else { // 스택이 비어있지 않다면 = 여는 괄호가 push되어 있음
					s.pop(); // 여는 괄호가 있다는 뜻이므로 pop
				}
			}
		} // 입력받은 하나의 문자열 탐색 종료
		if (!s.empty() || flag == 1) { // flag가 1로 세워져있거나, 스택이 비어있지 않다면
			cout << "NO" << endl;    // 짝이 맞지 않음
		}
		else {
			cout << "YES" << endl;
		}
		flag = 0; // 다시 flag를 초기화 해준 뒤 상위 for문으로 이동  
	}
	return 0;
}

 

 

스택은 대표적인 STL이므로 #include <stack>을 선언한 뒤, 이용한다.

문제 풀이

이 문제를 해결하는 알고리즘은 다음과 같다.

● 여는 괄호를 만나면

-> push

● 닫는 괄호를 만나면

-> 스택이 비어있는지 체크

-> 만약 비어있다면 여는 괄호보다 닫는 괄호가 더 많거나 먼저 나온 것이므로 Error

-> 만약 비어있지 않다면, 여는 괄호가 존재하고 닫는 괄호가 등장한 것이므로 짝이 맞음 -> pop

● 하나의 문자열에 대해 탐색이 끝났을 때

-> Error를 판단하는 flag값이 1로 셋팅 되어있다면 NO 출력

-> 또는 스택이 비어있지않다면 (= 괄호쌍이 맞지 않음) NO 출력

-> 위 Case에 해당하지 않는다면 올바른 쌍이므로 YES 출력

위 코드는 이중 for문을 사용했으므로 시간 복잡도는 O(N2)이라고 볼 수 있다.

---

참조

https://better-tomorrow.tistory.com/entry/c%EB%A1%9C-stack-%EA%B5%AC%ED%98%84STL-without-STL

stack 자료구조 설명 및 구현(c++)