백준 15926 현욱은 괄호왕이야!

https://www.acmicpc.net/problem/15926

15926번: 현욱은 괄호왕이야!!

이전에 괄호왕 문제를 풀었었는데 그거랑 비슷하다고 생각해서 만만하게 생각했습니다...ㅠ

이전 괄호왕이라는 문제에서는 그냥 stack에 push, pop이 전부 였는데 해당 문제는 조금 다른거 같습니다.

 

일단 배열을 사용해서 1로 만든다음에 1인 경우만 카운팅하는 아이디어를 떠올리지 못했습니다.

stack을 사용했으나 최대값을 찾으면서 pop을 할려는 로직을 구현을 하다보니 코드가 더 복잡하게 흘러 갔었습니다.

그냥 단순하게 앞으로 생각 해야 할거같습니다..ㅠ

 

짝을 만드는 문제는 보통 stack을 사용을 하는데 해당 문제도 똑같이 하면 되지만 가장 긴 짝의 수를 찾아야 합니다.

 

해당 문제를 풀수 있는 방법은 두가지 있습니다.

 

하나는, 배열을 사용해서 

(()))()()() 인경우 11110111111 이런식으로 가능 한 괄호는 1, 가능하지 않은 경우 0을 넣어 for문으로 돌려 가장 긴 MAX값을 찾는 방법이 있습니다.

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

#define endl "\n"

int n, d[200004], ret, cnt;
string str;
stack<int> stk;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> str;
    for (int i = 0; i < n; ++i)
    {
        // '(' 일 경우 바로 push한다.
        if (str[i] == '(') stk.push(i);
        else if (stk.size())
        {
            // ((( 가 stack에 있을 경우 ((( ))) 를 111 111 로 만들어 주는 로직
            d[i] = d[stk.top()] = 1;
            stk.pop(); 
        }
    }

    // 카운팅 하는 부분
    for (int i = 0; i < n; ++i)
    {
        if (d[i])
        {
            ++cnt;
            ret = max(ret, cnt);
        }
        else 
            cnt = 0;
    }

    cout << ret << endl;

    return 0;
}

 

다른 하나는 오로지 stack만을 사용하는 방법입니다.

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

#define endl "\n"

int n, d[200004], ret, cnt;
string str;
stack<int> stk;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> str;
    // 왜 -1 push하나?
    stk.push(-1);
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '(') stk.push(i);
        if (str[i] == ')')
        {
            stk.pop();
            
            // 스택이 비어 있지 않은 경우
            // ((())) 인 경우 3-1, 4-0, 5-(-1)을 하기 위해서
            if (!stk.empty()) ret = max(ret, i - stk.top());
            // 스택이 비어있는 경우
            else stk.push(i); 
        }
    }
    cout << ret << endl;
    return 0;
}