[ACM-ICPC][BOJ] 9012 - Parenthesis

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 'Parenthesis' 문제를 다뤄보겠습니다.

대표적인 스택 자료구조를 이용한 문제로 쉽게 풀 수 있었습니다.

---

[문제해석]

주어진 문자열이 괄호가 제대로 짝이 맞는지 안 맞는지 판단해서 맞는다면 "YES" 아니라면 "NO"를 출력해라.

 

[알고리즘설계]

( ( ) ) ( ) ) 같은 경우는 앞에 4개 (  (  ) )  와 그 뒤 2개  ( ) 는 짝이 맞지만 마지막 ) 의 짝꿍이 없으므로 NO이다.

이처럼 우리는 지금 주어진 괄호가 짝궁이 있는지 없는지 판단하면 된다.

 

1. Stack 자료구조를 이용해서, ' ( ' 인 경우에는 Stack에 넣고, ' ) ' 인 경우에는 Stack에서 하나를 꺼내서 짝꿍을 맺어준다. 이때, ' ) ' 인 경우지만 Stack이 비어있다면 짝꿍이 없는 경우이므로 'NO'를 출력하고 또, 끝까지 진행했는데 아직 Stack에 남아있는 ' ( ' 가 존재해도 짝궁이 없는 경우이므로 'NO'를 출력한다. 이 외에는 "YES"를 출력해준다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int ninput;
	cin >> ninput;
	for (int i = 0; i < ninput; i++) {
		stack<int> list;
		string input;
		cin >> input;
		int flag = 0;
		for (int j = 0; j < input.length(); j++) {
			if (input[j] == '(')
				list.push(j);
			if (input[j] == ')') {
				if (list.empty()) {
					cout << "NO\n";
					flag = 1;
					break;
				}
				else
					list.pop();
			}
		}
		if (list.empty() && flag == 0)
			cout << "YES\n";
		else if (!list.empty() && flag == 0)
			cout << "NO\n";
	}
}

Stack 자료구조를 배울 때, 같이 배우는 대표적인 문제라 금방 해결할 수 있었습니다.

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.