[백준][C++] 25918 북극곰은 괄호를 찢어

북극곰은 괄호를 찢어

25918. 북극곰은 괄호를 찢어

25918번: 북극곰은 괄호를 찢어

문제 풀이

 

보자마자 어!! 스택 문제!! 라고 생각했던 문제.

 

괄호만 보면 스택만을 외쳐대는 것 보니 나도 참 주입식 교육의 폐혜 같다...

아무튼 제대로 된 로직으로 푼 두번째 연세 문제!!

 

알고리즘 설계

1. 입력받은 괄호의 처음부터 끝까지 반복문을 돌려준다.

• 스택이 비어있을 때, 입력값이 (이나 )이라면 스택에 push한다.
• 스택의 top이 (이고, 현재 값이 )라면 스택을 pop한다.
• 반대로, 스택의 top이 )이고, 현재 값이 (라면 스택을 pop한다.

2. 최소 일수는 스택의 최대 크기로 한다.

()()()는 하루 안에 만들 수 있지만, ((()))는 3일이 걸리기 때문이다.

()()() =>
1 OOO

((()))=>
1 (O)
2 ((O))
3 ((()))

3. 1~2를 반복한다.

4. 반복문이 끝나고, 스택의 크기가 1 이상이라면 원하는 문자열을 만들 수 없음으로 인식해 -1을 출력한다.

5. 그렇지 않다면 최소 일수를 선택한다.

 

코드

#include<bits/stdc++.h>
using namespace std;

int main()
{
    stack<char> stack;
    string str;
    int result = 0;
    int len;
    cin >> len >> str;

    for (int i = 0; i < str.size(); i++)
    {
        // () => pop
        if (str[i] == '(' && !stack.empty() && stack.top() == ')')
        {
            stack.pop();
        }

        // ( => push
        else if (str[i] == '(')
        {
            stack.push(str[i]);
        }

        // )( => pop
        else if (str[i] == ')' && !stack.empty() && stack.top() == '(')
        {
            stack.pop();
        }

        // ) => push
        else if (str[i] == ')')
        {
            stack.push(str[i]);
        }

        result = max((int)stack.size(), result);
    }

    // 원하는 문자열을 만들지 못했다면 
    if (stack.size() > 0)
        cout << -1;
    else
        cout << result;
}

코드가 정갈하지는 않지만... 스택으로 잘 구현한 것 같아서 기분이 좋다 ^__^

스택의 가장 큰 사이즈를 result로 설정하는 아이디어는... 당시에는 어떻게 생각한지는 모르겠지만 좋은 아이디어 같다.