[백준 10799번] 쇠막대기

🔗알고리즘 문제

이 문제는 온전히 내 힘으로 해결하지 못하여 조금 내 자신에게 실망스러웠다,, 알고리즘 사고 능력을 좀 더 길러야겠다는 생각이 들었다.

문제 분석

이 문제는 다양한 길이의 쇠막대기를 레이저로 잘랐을 때 총 몇 개로 나뉘게 되는지 판단하는 문제이다.

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍인 '( )'로 표현된다. 모든 '( )'은 레이저를 표현한다.
쇠막대기의 시작점은 여는 괄호(이고 끝 점은 )닫는 괄호로 이루어져 있다.

( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) ) 이러한 입력이 주어졌을 때를 그림으로 알기쉽게 표현하면

이러한 모양이 되는데 이때 쇠막대기는 총 17조각으로 나뉘게 된다.

발상

괄호를 보자마다 스택문제다 !! 라고 떠올렸지만 간단한 변수만을 사용하여 문제를 해결할 수 있었다.

모든 쇠막대기는 ( ... )로 이루어져 있다. 즉 모든 쇠막대기의 시작은 ( 끝은 ) 라는 것을 알 수 있다.

현재 쇠막대기의 갯수를 담는 cnt라는 변수를 만들고 괄호가 열릴 때 증가 닫힐 때 감소 시켜준다.

만약, 레이저를 만날 경우에 쇠막대기의 갯수를 본다면 쇠막대기가 몇 번 나뉘게 되는지 알 수 있다.

레이저를 만나지 않을 경우에도 한 갈래가 생기게 되니 정답을 하나 증가시켜준다.

알고리즘 설계

1. 입력받은 값을 for문을 돌며 비교한다.
2. 만약 값이 '(' 라면 cnt를 증가시키고 ')'라면 cnt를 감소시킨다.
3. 만약 레이저를 만났다면 현재까지의 cnt값을 answer에 더해준다.
4. 레이저를 만나지 않았지만 현재 괄호가 닫혔다면 answer값을 증가시켜준다.

코드

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(){
    string input;
    int bar_count = 0;
    int answer = 0;

    cin >> input;

    for(int i = 0; i < input.length(); i++){
        if(input[i] == '('){
            bar_count++;
        }
        else{
            bar_count--;

            if(input[i - 1] == '('){
                answer += bar_count;
            }
            else{
                answer++;
            }
        }
    }

    cout << answer;
}