[백준 10799] 쇠막대기 (stack 활용)

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

10799번: 쇠막대기

 

1. 문제 분석

처음에는 문제를 읽고, 쇠막대기가 겹쳐있고.. 자기보다 길이가... 이런 긴 설명때문에 잠시 문제를 읽기가 싫어졌지만 다시 집중해서 읽어보니 복잡한 내용은 아니었다.

레이저와 쇠막대기의 배치를 '(', ')' 괄호를 이용한 한줄의 문자열로 주어지는데, 이를 해석해서 잘린 쇠막대의 총 개수를 알아내는 문제이다.

 

문제를 풀기 위해서는 먼저, 주어진 괄호가 쇠막대인지, 레이저인지 구분할 수 있어야 한다.

 

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 

 

따라서, 아래와 같은 규칙을 발견할 수 있다.

레이저가 등장 => 현재 겹쳐져있는 쇠막대기가 잘린다. 

레이저가 아닌 '('  등장=> 쇠막대기 하나가 추가로 겹쳐진다.

레이저가 아닌 ')' 등장 => 쇠막대기 하나의 길이가 끝난다.

 

또한 잘린 쇠막대기가 추가되는 시점도 함께 살펴 볼 수 있는데,

현재 겹쳐져 있는 쇠막대기의 개수를 N이라고 하고, 잘린 쇠막대기의 개수를 count라고 가정해보자.

 

레이저가 등장 => 현재 겹쳐져있는 쇠막대기가 잘린다.  (count += N)

레이저가 아닌 '('  등장=> 쇠막대기 하나가 추가로 겹쳐진다. (N += 1)

레이저가 아닌 ')' 등장 => 쇠막대기 하나의 길이가 끝난다. (count += 1, N -= 1)

 

▼쇠막대기 하나의 길이아 끝나는 시점에서 왜 count += 1을 하는 이유

(쇠막대기 하나의 길이가 끝나는 시점에서 왜 하나를 추가하는지 궁금할 수 도 있는데,

레이저로 쇠막대기를 커팅하면, 레이저를 기준으로 왼쪽과 오른쪽 각각에 잘린 쇠막대기로 나뉜다.

레이저가 등장했을 때, 현재 겹쳐져있는 쇠막대기를 자르고 count += N을 해주는데, 이는 왼쪽의 잘린 쇠막대기만 더한 값이므로 쇠막대기가 끝나는 시점에 오른쪽 잘린 쇠막대기를 하나 추가해주어야 한다.)

 

 

문제에서 주어진 예시를 위의 규칙에 따라 나타내보았다.

따라서, 입력으로 받아들인 괄호들의 배열을 레이저, 레이저가 아닌 '(', 레이저가 아닌 ')'로 분류하고 분류된 경우마다 count와 N의 값을 적절히 변경하는 코드를 작성하면 될것이다!

 

2. 코드 작성

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    vector<char> v;
    string str;
    cin >> str;
    int stick = 0;    //현재 겹쳐있는 쇠막대기의 개수
    int count = 0;    //커팅된 쇠막대기의 개수
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            v.push_back('(');
            stick++;
        }
            
        else if (str[i] == ')') {
            if (str[i - 1] == '(') { //레이저
                stick -= 1;
                count += stick;
            }
            else {    //쇠막대기의 끝
                stick--;
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
 
 
}

 

재미있는 문제였다. 끗