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

괄호 회전하기

문제 링크

괄호 회전하기

분석

문자열의 길이가 홀수일 경우 모든 회전에서 짝을 이룰 수 없습니다.

문자열이 회전될 때 첫번째 원소가 마지막 원소로 위치하게 됩니다.

가장 최근에 나온 여는 괄호를 기준으로 닫는 괄호가 나오는지 확인해야합니다.
"([])"의 경우 (다음으로 [가 오므로, 해당 괄호에 대해 순차적으로 저장해야합니다.
std::stack을 사용하면 좋습니다.

풀이

#include <string>
#include <stack>
#include <algorithm>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    // s의 길이만큼 순회
    for (int i = 0; i < s.length(); ++i)
    {
        // 여는 괄호에 대해 저장
        stack<char> st;
        
        // s의 원소에 접근하는 반복문
        for (char e : s)
        {
            // 짝이 맞는 경우
            if (!st.empty() && st.top() == '[' && e == ']')
            {
                st.pop();
            }
            else if (!st.empty() && st.top() == '{' && e == '}')
            {
                st.pop();
            }
            else if (!st.empty() && st.top() == '(' && e == ')')
            {
                st.pop();
            }
            // 여는 괄호일 경우, 짝이 맞지 않는 경우
            else
            {
                st.push(e);
            }
        }
        
        // 괄호가 모두 짝이 있는 경우
        if (st.empty())
        {
            ++answer;
        }
        
        // 문자열 회전
        rotate(s.begin(), s.begin() + 1, s.end());
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• s의 길이만큼 반복 $O(n)$
• s의 원소에 접근하는 반복문 $O(n)$
• s를 회전하는 rotate함수 $O(n)$
• $O(n \times n + n)$

공간 복잡도는 $O(n)$입니다.

• 스택에 최악의 경우 s의 모든 문자가 들어가므로 $O(n)$

테스트 1 〉 통과 (4.11ms, 3.68MB)
테스트 2 〉 통과 (5.12ms, 4.15MB)
테스트 3 〉 통과 (4.25ms, 3.64MB)
테스트 4 〉 통과 (3.45ms, 4.23MB)
테스트 5 〉 통과 (3.31ms, 4.09MB)
테스트 6 〉 통과 (3.43ms, 4.21MB)
테스트 7 〉 통과 (3.28ms, 4.21MB)
테스트 8 〉 통과 (3.32ms, 4.21MB)
테스트 9 〉 통과 (3.36ms, 4.16MB)
테스트 10 〉 통과 (3.72ms, 4.03MB)
테스트 11 〉 통과 (4.04ms, 4.16MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.45MB)