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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

괄호 회전하기

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

코딩테스트 연습 - 괄호 회전하기

문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

 

풀이

입출력 예시

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

풀이

괄호 문자열을 받아서 괄호 검사를 할 스택을 하나 만들어주자. 이곳에 괄호를 하나 하나 저장하면서 올바른 괄호 문자열인지를 체크해나갈 것이다.

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    stack<char> brck;
    string brckstr = s;
    
    return answer;
}

 

우선, 괄호의 회전을 만들어보자. 사실 회전이라 할 것은 없고 제일 앞에 있던 문자를 제일 뒤로 보내는 과정을 반복하면 된다.

 

...
    for (int h = 0; h < s.length(); h++) {
        // 괄호 검사 코드 들어갈 자리
        brckstr.push_back(brckstr[0]);
        brckstr.erase(0, 1);
    }
...

 

괄호를 검사할 차례이다. 스택에 하나하나 괄호를 push해주자. 만약, 괄호가 서로 매칭된다면 스택에서 빼주는 작업도 해주자. 시작이 ], }, )인 경우에는 과정을 다 생략하도록 해보자.

 

...
    ...
        for (int i = 0; i < brckstr.length(); i++) {
            if (brckstr[0] == ']' || brckstr[0] == '}' || brckstr[0] == ')') {
                break;
            }
            else {
                if (brck.empty()) { brck.push(brckstr[i]); } // 스택이 비었으면 바로 push
            
                // {, [, ( 와 }, ], )가 서로 매칭이 된다면 스택에서 pop해주기
                else if (brck.top() == '{' && brckstr[i] == '}') {
                    brck.pop();
                }
                else if (brck.top() == '[' && brckstr[i] == ']') {
                    brck.pop();
                }
                else if (brck.top() == '(' && brckstr[i] == ')') {
                    brck.pop();
                }
                else { //만약 아무것도 매칭되지 않으면 바로 push
                    brck.push(brckstr[i]);
                }
            }
        }
    ...
...

 

마지막 문자열까지 처리가 완료되었다면, 이제 올바른 괄호 문자열이었는지를 알아야한다. 올바른 괄호 문자열이었다면 스택이 지금 비어있을 터이므로, 스택이 비어있다면 카운트해주자.

 

...
    ...
        ...
            if (i == brckstr.length() - 1) {
				if (brck.empty()) {
					answer++;
				}
				else {
					while (!brck.empty()) {
						brck.pop();
					}
				}
			}
        ...
    ...
...

전체 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    stack<char> brck;
    string brckstr = s;
    
    for (int h = 0; h < s.length(); h++) {
        for (int i = 0; i < brckstr.length(); i++) {
            if (brckstr[0] == ']' || brckstr[0] == '}' || brckstr[0] == ')') {
                break;
            }
            else {
                if (brck.empty()) { brck.push(brckstr[i]); } // 스택이 비었으면 바로 push
            
                // {, [, ( 와 }, ], )가 서로 매칭이 된다면 스택에서 pop해주기
                else if (brck.top() == '{' && brckstr[i] == '}') {
                    brck.pop();
                }
                else if (brck.top() == '[' && brckstr[i] == ']') {
                    brck.pop();
                }
                else if (brck.top() == '(' && brckstr[i] == ')') {
                    brck.pop();
                }
                else { //만약 아무것도 매칭되지 않으면 바로 push
                    brck.push(brckstr[i]);
                }
            }
            if (i == brckstr.length() - 1) {
                if (brck.empty()) {
                    answer++;
                }
                else {
                    while (!brck.empty()) {
                        brck.pop();
                    }
                }
            }
        }
        brckstr.push_back(brckstr[0]);
        brckstr.erase(0, 1);
    }
    
    return answer;
}