괄호 회전하기 / stack 사용

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

 

다른 것 보다 괄호 안에 괄호가 있을 때의 경우를 어떻게 검증할지에 대해 고민이 많았던 문제다.

FIFO 구조의 stack 자료구조로 괄호를 앞에서부터 하나씩 추가해가며 맞는 올바른 괄호가 생기면 삭제하는 방식으로 문제를 해결했고, stack이 비어있게 되면 현재 회전된 문자열 s가 올바른 괄호로 이루어진 문자열이 됨을 검증하였다.

 

 

✅구현 코드

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

using namespace std;

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

    for (int i = 0; i < s.length(); ++i)
    {
        // s를 회전해서 temp에 저장
        string temp = s.substr(i) + s.substr(0, i);
        // 올바른 괄호 검증하기 위해 stack 선언
        stack<int> st;

        for(char c : temp)
        {
            // 현재 문자 c가 괄호의 시작이거나 스택이 비어있을 경우 푸쉬
            if (c == '[' || c == '{' || c == '(' || st.empty())
            {
                st.push(c);
            }
            else
            {
                // 앞서 스택에 저장된 괄호가 닫는 괄호라면 올바른 괄호가 아니므로 break
                if (st.top() == ']' || st.top() == '}' || st.top() == ')') break;

                // 짝이 맞는 괄호일 경우
                // 닫는 괄호 - 여는 괄호 일때 아스키코드 값 기준으로 2 이하의 수가 나옴
                // 이것으로 올바른 괄호인지 검증
                if ((c - '0') - (st.top() - '0') <= 2) st.pop();

                // 괄호 안에 괄호가 존재할 수 있음으로 일단 푸쉬
                else st.push(c);
            }
        }

        // stack이 비어있다면 모두 올바른 괄호임으로 answer 증가
        if (st.empty()) answer++;
    }

    return answer;
}

 

📍 코드 흐름

• 문자열 회전을 queue를 사용하지 않고 string::substr을 사용해 회전 시켜주었다.
  • substr(i): i 인덱스부터 문자열의 끝까지 도출
  • substr(0, i): 0번 인덱스부터 i 개수만큼의 문자열 도출
  • string temp = substr(i) + substr(0,i): 현재 i 인덱스부터 문자열의 끝까지 도출된거에 회전된 앞부분을 뒤에 더함

// s를 회전해서 temp에 저장
string temp = s.substr(i) + s.substr(0, i);

 

• 현재 문자 c가 여는 괄호이거나 스택이 비어있다면, 스택에 현재 문자 c를 저장

 // 현재 문자 c가 괄호의 시작이거나 스택이 비어있을 경우 푸쉬
 if (c == '[' || c == '{' || c == '(' || st.empty())
 {
     st.push(c);
 }

 

• 스택에 저장된 문자열이 있을 경우 
• 만약 닫는 괄호가 스택의 top이라면 올바른 괄호가 아니므로 반복문을 break 한다.
• 아스키 코드 기준으로 '닫는괄호 - 여는 괄호' 의 값은 2가 된다.
• 이것으로 올바른 괄호인지 판별하고 맞다면 스택의 top을 제거하고 다음으로 넘어간다.
• 만약 스택의 top이 여는괄호이고, 현재 문자 c도 여는괄호라면, 괄호안의 괄호가 있을 수 있으므로 일단 push
• 이 과정의 루프가 끝났을 때, stack이 비어있다면 모두 올바른 괄호임이 검증된다.

else
{
    // 앞서 스택에 저장된 괄호가 닫는 괄호라면 올바른 괄호가 아니므로 break
    if (st.top() == ']' || st.top() == '}' || st.top() == ')') break;

    // 짝이 맞는 괄호일 경우
    // 닫는 괄호 - 여는 괄호 일때 아스키코드 값 기준으로 2 이하의 수가 나옴
    // 이것으로 올바른 괄호인지 검증
    if ((c - '0') - (st.top() - '0') <= 2) st.pop();

    // 괄호 안에 괄호가 존재할 수 있음으로 일단 푸쉬
    else st.push(c);
}

// stack이 비어있다면 모두 올바른 괄호임으로 answer 증가
if (st.empty()) answer++;