[Programmers] 76502번 - 괄호 회전하기 [Java][C++]

문제 링크

---

1. 아이디어

올바른 괄호 문자열을 판단하는 문제로 올바른 괄호 문자열은 괄호들로 이루어진 문자열이 유효한 괄호 규칙을 이루는 문자열이다. 괄호 문제를 해결하는 대표적인 기법인 스택 자료구조를 활용해서 해결했는데 열린 괄호열이면 스택에 담고 닫힌 괄호열이면 스택의 top에 위치한 괄호와 쌍이 맞는지 판단해서 쌍이 맞으면 해당 괄호를 스택에서 제거하고 쌍이 안맞으면 괄호 규칙을 만족하지 않음을 활용하면 된다. 이때 괄호 문자열이 회전도 하는데 이는 반복문과 모듈러 트릭을 활용해서 회전한 것처럼 괄호열에서 포인터를 이동하는 방식으로 해결할 수 있다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(N^2)$	$O(N)$

$N$ = 문자열 s 길이

---

3. 코드

풀이 [Java][C++]

import java.util.*;

class Solution {
    public int solution(String s) {
        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            Deque<Character> stk = new ArrayDeque<>();
            boolean flag = true;

            for (int j = i; j < i + s.length(); j++) {
                char c = s.charAt(j % s.length());

                if (c == '(' || c == '{' || c == '[') {
                    stk.push(c);
                } else {
                    if (stk.isEmpty()) {
                        flag = false;
                        break;
                    } else if (c == ')') {
                        if (stk.peek() == '(') {
                            stk.pop();
                        } else {
                            flag = false;
                            break;
                        }
                    } else if (c == '}') {
                        if (stk.peek() == '{') {
                            stk.pop();
                        } else {
                            flag = false;
                            break;
                        }
                    } else if (c == ']') {
                        if (stk.peek() == '[') {
                            stk.pop();
                        } else {
                            flag = false;
                            break;
                        }
                    }
                }
            }

            if (!stk.isEmpty()) {
                flag = false;
            }

            if (flag) {
                ans++;
            }
        }

        return ans;
    }
}

#include <stack>
#include <string>

using namespace std;

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

    for (int i = 0; i < s.size(); i++) {
        stack<char> stk;
        bool flag = true;

        for (int j = i; j < i + s.size(); j++) {
            char c = s[j % s.size()];

            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            } else {
                if (stk.empty()) {
                    flag = false;
                    break;
                } else if (c == ')') {
                    if (stk.top() == '(') {
                        stk.pop();
                    } else {
                        flag = false;
                        break;
                    }
                } else if (c == '}') {
                    if (stk.top() == '{') {
                        stk.pop();
                    } else {
                        flag = false;
                        break;
                    }
                } else if (c == ']') {
                    if (stk.top() == '[') {
                        stk.pop();
                    } else {
                        flag = false;
                        break;
                    }
                }
            }
        }

        if (!stk.empty()) {
            flag = false;
        }

        if (flag) {
            ans++;
        }
    }

    return ans;
}

---