[C++] Programmers Lv. 2 "괄호 회전하기"

🔵 문제 링크

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

프로그래머스

🔵 문제 유형

괄호 짝을 찾는 문제이니 stack을 자연스레 떠올렸다.

 

💡 Point

• 문자열을 회전시키는 법
• 괄호 종류별 손쉽게 대처하는 법

 

🔷 문자열을 회전시키는 법

처음에는 deque를 사용하여 제일 앞에 있는 것을 pop 하여 맨 뒤에 push 하는 방법을 생각했었다.

하지만 뭔가 번거로웠고 머릿속으로 "이것보다 간단하게 할 수 있을 것 같은데..."라는 생각이 나서 방법을 찾아보았다.

찾은 방법은 다음과 같다.

 

start index를 두어 이를 증가시키면서 배열을 순회하는 것이다. 이때, 모듈러 연산을 사용한다.

start index에서 점차 값을 증가하면서 배열의 순회할 때 배열의 크기를 넘어가지 않고 처음으로 돌아가야 하기 때문이다.

    // n은 s.size()
    for (int i = 0; i < n; i++)
    {
        // 회전
        char c = s[(start + i) % n];

 

🔷 괄호 종류별 손쉽게 대처하는 법

unordered_map을 사용했다. (닫힌 괄호(key) - 열린 괄호(value))

// 괄호 쌍 데이터화 
unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} };

 

이렇게 하면 unordered_map.count() 연산으로 현재 문자가 닫힌 괄호인지 ( == key 값인지) 바로 확인할 수 있고,

다음 괄호가 알맞은 짝인지 unordered_map[현재 닫힌 괄호]로 간편하게 알 수 있다.

 

🔵 전체 코드

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

using namespace std;

// 괄호 쌍 데이터화 
unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} };

bool IsValid(string &s, int start)
{
    // 괄호 쌍을 찾기 위해 스택 활용
    stack<char> stk;
    int n = s.size();

    for (int i = 0; i < n; i++)
    {
        // 회전
        char c = s[(start + i) % n];

        // 닫힌 괄호
        if (pairs.count(c))
        {
            // 스택이 비었거나 스택 맨 위가 닫힌 괄호의 쌍과 맞지 않을 때 -> 실패
            if (stk.empty() || stk.top() != pairs[c])
                return false;

            stk.pop();
        }
        // 열린 괄호
        else
        {
            stk.push(c);
        }
    }

    return stk.empty();
}

int solution(string s) {
    int answer = 0;
    
    for (int i = 0; i < s.size(); i++)
    {
        answer += IsValid(s, i);
    }

    return answer;
}

 

🔵 시간 복잡도

총 for문을 2개 돌게 되는데, 둘 다 input인 's'의 길이에 영향을 받는다.

따라서 s의 길이를 N이라 할 때, 시간 복잡도는 O(N^2)이다.