[코딩테스트 40일차] BAEKJOON 9012번 : 괄호

[BAEKJOON 9012번 : 괄호]

[문제]

---

[고찰]

저는 해당 문제에 대해서 정수형 count 변수를 선언한 후, ' ( '가 나오면 count++을 해주고, ' ) '가 나오면 count--를 해주는 방식으로 하여 count가 0일 때 해당 문자열이 VPS라는 아이디어로 풀었습니다.

 

다만, 다른 분들의 풀이를 보니 스택으로 해당 문제를 풀었고, 문제의 알고리즘 분류에도 스택이 있어 스택으로도 풀어보려고 합니다.

 

아래는 괄호를 카운트하는 방식으로 푼 제 코드입니다.

#include <iostream>
#include <string>    

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	while (t--)
	{
		string str;
		int count = 0;

		cin >> str;

		for (char c : str)
		{
			if (c == '(')
				count++;
			if (c == ')')
				count--;

			if (count < 0)
				break;
		}

		cout << ((count == 0) ? "YES" : "NO") << '\n';
	}

	return 0;
}

---

[개념]

먼저 스택의 개념을 정리하고자 합니다.

 

Stack

스택은 컨테이너 어댑터(Container Adapter)입니다.

이는 특정 컨테이너의 기능을 제한하여 특정 데이터 구조의 인터페이스를 제공하는 클래스입니다.

 

문법

#include <stack>

stack<int> s;      // int형 스택
stack<string> st;  // string형 스택

 

stack은 <stack> 헤더에 정의되어 있으며,

LIFO (Last In, First Out), 후입선출의 구조로, 마지막에 넣은 데이터가 가장 먼저 나오는 자료구조입니다.

---

템플릿 매개변수

template <class T, class Container = std::deque<T>>
class stack;

• T : 스택에 저장될 요소의 타입입니다.
• Container : 스택의 내부 구현에 사용될 컨테이너의 타입입니다. 기본값은 std::deque<T>입니다.
  • 해당 매개변수에 std::deque<T> 대신 std::vector<T>나 std::list<T>를 지정할 수 있습니다.

---

주요 함수

• st.push(x) : 스택의 맨 위에 x를 추가
• st.pop( ) : 맨 위 요소 제거
• st.top( ) : 맨 위 요소 반환
• st.empty( ) : 스택이 비어있는지 확인하여 true 또는 false 반환
• st.size( ) : 현재 스택에 들어있는 요소 개수 반환

---

이제 스택을 활용하여 해당 문제를 푸는 방법을 정리해보겠습니다.

 

char형 스택을 생성한뒤, 입력 받은 문자열을 for문으로 반복하면서, ' ( '면 push, ' ) '면 pop을 하는 것이 기본 아이디어입니다.다만, ' ) '일 때, 스택이 비어있다면 카운트 방식으로 따졌을 때 count가 0 이하가 되는 것이기 때문에, 이때는  push를 해주고 for문 반복을  break를 통해 멈춰줍니다.

 

이후 스택이 비었는지 안비었는지에 따라 YES 또는 NO를 출력해주면 됩니다.

 

이를 코드로 표현하면 아래와 같습니다.

stack<char> st;
string str;

cin >> str;

for (char c : str)
{
	if (c == '(')
	{
		st.push(c);
	}
	else
	{
		if (st.empty())
		{
			st.push(c);
			break;
		}
		st.pop();
	}
}

cout << (st.empty() ? "YES" : "NO") << '\n';

---

[정리]

실버 4가 되니, 슬슬 자료구조에 대해 나오는 것 같습니다.

앞으로 컨테이너 클래스 템플릿에 관해서도 정리해야겠습니다.

---

[Solution]

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	while (t--)
	{
		stack<char> st;
		string str;

		cin >> str;

		for (char c : str)
		{
			if (c == '(')
			{
				st.push(c);
			}
			else
			{
				if (st.empty())
				{
					st.push(c);
					break;
				}
				st.pop();
			}
		}

		cout << (st.empty() ? "YES" : "NO") << '\n';
	}

	return 0;
}