[Programmers] 괄호 회전하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

 

---

 

문제 해결 과정

착안

스택(stack) 자료 구조를 활용하여 다음과 같은 과정을 통해 괄호 문자열 여부를 판단하고, 해당 과정을 회전된 문자열에 대해서 반복 수행함으로써 괄호 문자열의 수를 카운팅한다.

 

• '(', '{', '[' 문자가 주어지는 경우: 스택에 해당 문자를 추가한다.
• ')', '}', ']' 문자가 주어지는 경우: 스택이 비어있거나 스택의 top에 위치한 문자가 괄호로 짝지어지지 않는 경우 false를 반환한다. 그렇지 않다면 스택에서 top에 위치한 문자를 제거한다.
• 모든 문자열에 대해 위의 과정이 끝난 다음 스택이 비어있으면 true, 그렇지 않다면 false를 반환한다.

 

구현

주어진 길이 $n$의 괄호 문자열을 회전시키는 과정은, 편의상 주어진 문자열을 복사하여 뒤에 이어 붙인 뒤 해당 문자열의 $i$번째부터 시작하는 길이 $n$의 부분 문자열을 구하는 substr() 함수를 활용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <stack>

using namespace std;

stack<char> Stack;

bool decision(string s)
{
	for (char c : s)
	{
		switch (c)
		{
			case '(': case '{': case '[':
			{
				Stack.push(c);
				break;
			}
			
			case ')':
			{
				if (Stack.empty() || Stack.top() != '(') return false;
				Stack.pop();
				break;
			}

			case '}':
			{
				if (Stack.empty() || Stack.top() != '{') return false;
				Stack.pop();
				break;
			}

			case ']':
			{
				if (Stack.empty() || Stack.top() != '[') return false;
				Stack.pop();
				break;
			}
		}
	}

	return Stack.empty();
}

int solution(string s)
{
	int answer = 0;
	int n = s.size();

	s += s;
	for (int i = 0; i < n; i++)
		if (decision(s.substr(i, n)))
			answer++;

	return answer;
}

 

실행 결과