<프로그래머스 C++> 괄호 회전하기 풀이 (stack)

문제

대괄호, 중괄호, 소괄호로 이루어진 문자열 s를 왼쪽으로 x칸 회전했을 때 올바른 괄호 문자열이 되는 x의 개수를 return하는 문제이다.

---

풀이 아이디어

이 문제의 핵심 포인트는 두 가지이다.

 

1. 문자열 회전

x칸을 회전하는 것은 왼쪽 앞부분을 잘라 뒤에 붙이면 된다.

"[](){}" 를 2칸 회전
뒷부분: s.substr(2)    = "(){}"
앞부분: s.substr(0, 2) = "[]"
회전 결과 = "(){}" + "[]" = "(){}[]"

string rotated = s.substr(x) + s.substr(0, x);

 

2. 올바른 괄호 판별 (스택 사용)

여는 괄호를 stack에 push, 닫는 괄호는 스택의 top과 짝이 맞는지 확인한다.

모든 문자를 처리한 후, 스택이 0이 되면 올바른 괄호라고 판단한다.

 

닫는 괄호가 나왔는데 스택이 비어있다면 false이다.

스택 top이 대응하는 여는 괄호가 아니여도 false이다.

"([)]" 경우
( → push
[ → push
) → top이 [ → 짝 불일치 

")(" 경우
) → 스택 비어있음 → 즉시

---

문제 풀이

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

bool IsValid(string s)
{
    stack<char> st;
    for(char c : s)
    {
        if(c == '(' || c == '[' || c == '{')
            st.push(c);
        else
        {
            if(st.empty()) return false;
            char top = st.top();
            st.pop();
            if(c == ')' && top != '(') return false;
            if(c == ']' && top != '[') return false;
            if(c == '}' && top != '{') return false;
        }
    }
    return st.empty();
}

int solution(string s) {
    int answer = 0;

    for(int i = 0; i < s.size(); ++i)
    {
        string rotated = s.substr(i) + s.substr(0, i);
        if(IsValid(rotated))
            answer++;
    }
    return answer;
}

---

코드 흐름

1. 문자열 회전

string rotated = s.substr(i) + s.substr(0, i);

i칸 회전한 문자열을 만든다.

s.substr(i)는 i번째부터 끝까지, s.substr(0, i)는 앞에서부터 i까지이다. 두 개를 합치면 i칸 왼쪽으로 회전한 결과가 나온다.

 

2. 여는 괄호 push

if(c == '(' || c == '[' || c == '{')
    st.push(c);

여는 괄호를 stack에 push한다.

 

3. 닫는 괄호 체크

if(st.empty()) return false;
char top = st.top();
st.pop();
if(c == ')' && top != '(') return false;
if(c == ']' && top != '[') return false;
if(c == '}' && top != '{') return false;

닫는 괄호가 나오면 두 가지를 체크한다.

 

1. 스택이 비어있는가?

→ 스택이 비어있으면 짝이 없는 괄호이다.

 

2. 스택 top이 대응하는 여는 괄호가 아닌가?

→ 이 경우에는 괄호가 일치하지 않는 것.

 

4. 최종 판별

return st.empty();

모든 문자를 처리한 후 스택이 비어있으면 올바른 괄호이다. 이 경우에 IsValid()함수에서 true를 반환한다.

---

핵심포인트

 

• x칸 회전은 s.substr(x) + s.substr(0, x)로 구현한다.
• 괄호 판별은 스택으로한다. 여는 괄호는 push, 닫는 괄호는 top과 짝 확인 후 pop한다.
• 닫는 괄호 체크 시 스택이 비어있는 경우도 반드시 처리해야 한다.