[BOJ알고리즘, C++]#10799_쇠 막대기, 선형 자료구조, 스택

 

[BOJ알고리즘, C++]#10799_쇠 막대기

 

BOJ 알고리즘 문제 풀이, 10799번 문제 "쇠 막대기"

C++의 STL이 제공하는 stack 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

• [정의] : 스택은 후입선출 방식으로 동작하는 선형 자료구조입니다. 스택은 동일한 크기와 유형의 데이터를 정해진 한 방향으로만 삽입/삭제가 가능합니다.

 

2. stack 컨테이너

[Basic C++] #64_stack

 

3. ')' + ')' 조합? '(' + ')' 조합?

1. 먼저, 주어진 문자열을 차례대로 순회하며, 현재 위치의 원소가 '('일 경우, 스택에 삽입합니다. 이는 현재 이어지고 있는 막대 개수를 세기 위함입니다. 
2. ')'일 경우 직전 위치의 항목을 살펴봅니다.
3. 첫 번째로 직전 위치의 문자가 '('일 경우, 인접한 괄호 쌍이 발견되어 '레이저'로 취급합니다.
4. 두 번째로 직전 위치의 문자가 ')'일 경우, 인접한 괄호 상이 아니기 때문에 어느 한 막대기의 끝 부분으로 취급합니다.
5. 첫 번째의 경우, 레이저가 발사되어 막대가 절단되므로, stack.size() 만큼의 막대가 추가적으로 생성됩니다. 따라서, 막대의 총합에 + stack.size()를 해줍니다.
6. 두 번째의 경우, 막대의 끝이 발견되어, 더 이상 절단되지 않기 때문에 stack.pop()을 통해 stack에 쌓여있는 '(' 열린 괄호를 제거합니다. 이때, 막대의 절단은 발생하지 않았지만, 절단 이후에 생긴 막대가 아직 합계에 반영되지 않았기 때문에 총막대의 총합에 +1해 줍니다. 

 

#3. 코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    string str;
    cin >> str;
    
    // 스택 선언, 첫 번째 항목 삽입
    stack<char> s;
    s.push(str[0]);
    
    int ans = 0;
    for(int i=1; i<(int)str.size(); i++)
    {
        // #1. ')'를 만났을 경우
        if(str[i] == ')')
        {
            s.pop();
            // #1. 레이저 일 경우
            if(str[i-1] == '(')
            {
                // stack.top() 제거 후 ans += s.size()
                ans += s.size();   
            }
            // #2. 막대기 끝일 경우
            else
            {
                // stack.top() 제거 후 ans += 1 
                ans++;
            }
        }
        // #2. '('를 만났을 경우
        else if(str[i] == '(')
        {
            s.push(str[i]);
        }
    }
    
    cout << ans;
    
    return 0;
    
}