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

문제

 

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

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

문제풀이

 

스택을 이용하여 풀었다. 괄호의 종류가 세 가지나 있다.

s의 최대 크기가 많이 안 커 보이므로 회전 대신 s를 덧붙이고 idx만 늘리면서 회전의 역할을 한다.

문자열을 바꿀 때마다 스택을 초기화한다.

 

여는 괄호가 들어오면 스택에 push 한다.

 

닫는 괄호가 들어오면 스택이 비었는지, 안 비었는지를 확인한다.

스택이 비어있다면 짝이 맞을 수 없으므로 바로 break를 한다.

 

스택이 비어있지 않다면 짝이 맞는 괄호인지 판별해야 한다.

')'가 들어오면 '(', '{'가 들어오면 '}', '['가 들어오면 ']'.

(아스키코드 값이 (랑 )은 1이 차이 나는데 나머지 중, 대괄호는 2가 차이 난다.)

 

그 외의 경우는 짝이 안 맞는 괄호이므로 else로 걸러져 break 된다.

 

반복문이 종료되었으면, 해당 문자열이 올바른 괄호였으면 스택이 비어져있어야 하므로 해당 조건을 걸어 판별한다.

코드

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

int solution(string s) {
    int answer(0), idx(0), idx2(0);
    s += s;
    stack<char>bracket;
    for (idx = 0; idx < s.size() / 2; ++idx) {
        bracket = stack<char>();
        for (idx2 = idx; idx2 < s.size() / 2 + idx; ++idx2) {
            if (s[idx2] == '(' || s[idx2] == '{' || s[idx2] == '[') {
                bracket.push(s[idx2]);
            }
            else if (!bracket.empty()) {
                if (bracket.top() == '(' && s[idx2] == ')') {
                    bracket.pop();
                }
                else if (bracket.top() + 2 == s[idx2]) {
                    bracket.pop();
                }
            }
            else {
                break;
            }

        }
        if (idx2 == s.size() / 2 + idx && bracket.empty()) {
            answer++;
        }
    }
    return answer;
}