[프로그래머스 C++] 괄호 회전하기

 

[프로그래머스 C++] 괄호 회전하기

 

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

프로그래머스

---

 

 

해결방안

 

구현

문자열

스택 Stack

큐, 데큐 Queue, Deque

 

---

 

 

코드

 

#include <vector>
#include <string>
#include <deque>
#include <stack>
using namespace std;

bool isMatch(char a, char b)
{
	if (a == '[' && b == ']') return true;
	if (a == '{' && b == '}') return true;
	if (a == '(' && b == ')') return true;

	return false;
}

int solution(string s) {
	int answer = 0;  
	int n = s.size(); 
    
	deque<char> DQ(s.begin(), s.end()); 

	while(n--)
	{
		stack<char> st; 
        
		for (char bracket : DQ) 
		{
			if (bracket == '[' || bracket == '{' || bracket == '(')
				st.push(bracket);
			
			else 
			{	
				if(st.empty() || isMatch(st.top(), bracket) == false)
				{
					st.push(bracket);	
					break;				
				}
				st.pop();
			}
		}

		if (st.empty()) answer++; 

		char temp = DQ.front();
		DQ.pop_front();
		DQ.push_back(temp);
	}


	return answer;
}

 

 

 

---

 

코드 및 해설

 

#include <vector>
#include <string>
#include <deque>
#include <stack>
using namespace std;

// 두 개의 입력된 괄호가 서로 짝을 이루는지를 확인하는 함수
// (, {, [와 ), }, ]가 적절히 짝을 이루는지 확인
bool isMatch(char a, char b)
{
	if (a == '[' && b == ']') return true;
	if (a == '{' && b == '}') return true;
	if (a == '(' && b == ')') return true;

	return false;
}

int solution(string s) {
	int answer = 0;  // 올바른 괄호 문자열의 개수를 저장할 변수
	int n = s.size(); // 주어진 문자열의 길이

	// 왼쪽 회전을 용이하게 하기위해 deque 사용.
	deque<char> DQ(s.begin(), s.end()); //문자열 s를 deque에 넣습니다.

	while(n--)
	{
		stack<char> st; //괄호 검사에 사용할 스택
	
		//현재의 문자열이 올바른 괄호 문자열인지 확인하기 위해 st을 이용한다.
		for (char bracket : DQ) //DQ의 요소들을 순회 
		{
			if (bracket == '[' || bracket == '{' || bracket == '(')
				st.push(bracket); //여는 괄호면 스택에 푸시
			
			else 
			{	// st가 비워져있고 다음 괄호가 ']', '}', ')' 라면
				// st의 맨 위 원소와 다음 괄호가 같지 않다면
				if(st.empty() || isMatch(st.top(), bracket) == false)
				{
					st.push(bracket);	// 괄호를 st에 넣고
					break;				// 종료
				}
				// 위의 조건이 아니라면
				// =st.top의 괄호와 대응되는 괄호가 있으면 st에서 꺼낸다.
				st.pop();
			}
		}
		
        // 여는 괄호일 경우 스택에 푸시하고, 닫는 괄호일 경우 가장 최근에 푸시된 여는 괄호와 비교하여 짝이 맞으면 스택에서 제거. 
        // 만약 짝이 맞지 않거나 스택이 비어있으면 닫힌 괄호를 스택에 넣고 반복문을 종료.
		if (st.empty()) answer++; //stack이 비었으면 올바른 괄호 문자열이다.

		//왼쪽으로 회전
		char temp = DQ.front();
		DQ.pop_front();
		DQ.push_back(temp);
	}


	return answer;
}

 

 

---