[프로그래머스] 2단계 - 괄호 회전하기

문제 설명

( ), [ ], { } 가 짝을 맞춰있는 것을 올바른 괄호 문자열이라고 한다

문자열 s를 x칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 

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

프로그래머스

 

문제 풀이법

괄호 관련된 문제가 나오면 거의 stack을 이용해 푸는 것 같다

이번에도 스택을 통해 문제를 풀었다 

 

문자열 s를 회전한다는 말은 만일 문자열이 'hello' 인 경우 'hello' -> 'elloh' -> 'llohe'..... 이런 식으로 회전시킨다는 말이다

 

즉, 문자열의 길이만큼 첫번째 인덱스를 달리하여 올바른 문자열인지 검사하면 된다

 

문자열을 순회하며, 문자가 (, [, { 면 스택에 push를 한다

문자가 ), ], } 면 우선 스택이 비어있지 않는지 확인을 하고 비어있으면 잘못된 문자열이므로 flag를 false 처리한다

스택이 비어있지 않다면 각 괄호가 짝이 맞는지 확인하고 짝이 맞으면 pop 한다

문자열을 다 돌면 스택이 비어있는지 확인하고, 비어있지 않다면 flag를 false 처리하여 최종적으로 flag가 true이면 answer++ 해준다

 

이때 문자열은 순회를 해야하므로 같은 코드로 for문을 2번 도는데 첫번째는 0부터 반복하는 for문이고, 두번째는 첫번째 for문이 수행하지 않는 인덱스를 수행하는 for문이다

즉 맨 처음의 for문의 j가 3이고, len이 5라면

s[3] - s[4] - s[0] - s[1] - s[2]로 돌아가게 하는 구문이다

 

(사실 똑같은 코드를 2번 쓰는것이 싫어서 인덱스는 무조건 0부터 시작하고 문자열 s를 잘라서 뒤에 붙이는 방법도 생각했는데, 어차피 시간복잡도는 동일할 것 같아서 하지 않았다)

 

 

소스 코드

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

using namespace std;

int solution(string s) {
    int answer = 0;
    int len = s.size();
    
    for (int i = 0; i < len; i++) {
        stack<char> st;
        bool flag = true;
        
        for (int j = i; j < len; j++) {
            if (flag == false)
                break;
            
            if (s[j] == '[' || s[j] == '(' || s[j] == '{')
                st.push(s[j]);
            else {
                if (st.empty())
                    flag = false;
                else {
                    if ((s[j] == ']' && st.top() == '[') ||
                        (s[j] == ')' && st.top() == '(') ||
                        (s[j] == '}' && st.top() == '{'))
                        st.pop();
                }
            }
        }
        
        for (int j = 0; j < i; j++) {
            if (flag == false)
                break;
            
            if (s[j] == '[' || s[j] == '(' || s[j] == '{')
                st.push(s[j]);
            else {
                if (st.empty())
                    flag = false;
                else {
                    if ((s[j] == ']' && st.top() == '[') ||
                        (s[j] == ')' && st.top() == '(') ||
                        (s[j] == '}' && st.top() == '{'))
                        st.pop();
                }
            }
        }
        
        if (!st.empty())
            flag = false;
        
        if (flag == true)
            answer++;
            
    }
    
    return answer;
}