[BOJ]10799번: 쇠막대기(c++)

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

10799번: 쇠막대기

 

방법 1: 스택이용

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    string input;
    getline(cin, input);
 
    stack<int> s;
 
    int answer = 0;
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == '(')
        {
            s.push(i);
        }
        else
        {
            // stack top의 인덱스와 1차이 나면 레이저.
            if ((i - s.top()) == 1)
            {
                s.pop();
                answer += s.size();
            }
            else
            {
                s.pop();
                answer++;
            }
        }
    }
 
    cout << answer;
 
    return 0;
}

 

 

방법 2: 벡터에 자른 갯수 저장

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    string input;
    getline(cin, input);
    vector<int> v(input.size(), 0);
 
    int idx = 0;
    int answer = 0;
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == '(')
        {
            v[idx++] = 1;
        }
        else
        {
            idx--;
            
            // 레이저일때. 유효한 벡터 요소들을 1씩 더해줌.
            if (input[i - 1] == '(')
            {
                for (int j = 0; j < idx; j++)
                {
                    v[j]++;
                }
            }
            // 일반 닫는 괄호일때. 해당 벡터요소를 합산.
            else
            {
                answer += v[idx];
            }
        }
    }
 
    cout << answer;
 
    return 0;
}

 

 

방법1 스택 사용한 답안이 훨씬 효율적이다

 

 

가독성도 그렇고, 스택 사용이 훨씬 낫다!