[Silver II] 쇠막대기 - 10799

쇠막대기 (https://www.acmicpc.net/problem/10799)

문제를 읽어보시면 숨이 턱 막히며 어렵다 라고 생각하실 수 있습니다!! 하지만 처음엔 누구나 다 어렵고 힘듭니다. 걱정하지 마세요 정상입니다 :)

이번에도 똑같이 문제 설명을 한번 읽어보시고

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

이 내용이 중요해보입니다.

이 문제의 핵심은 사실 () 안에 얼마나 많은 ‘(’ 그리고 ‘)’가 있는가? 입니다.

해당 문제 이미지입니다.

한번 세볼까요?

정말 17개네요!

그리고 각 괄호는 이렇게 대응이 되고 있습니다.

여기서

이 부분을 한번 볼까요? 레이저 양 옆에 괄호가 둘러싸여있습니다.

그리고 레이저가 반으로 자르니까 2개의 조각이 나오게 됩니다.
이걸 코드로 구현하면 어떻게 해야 할까요?


제 생각엔 레이저를 만나기 전까지 ‘(’ 의 개수와 마지막 닫는 ‘)’ 의 개수를 더해줄 것 같습니다.
그러면 딱 2개가 나오니깐요.
이 원리로 하나하나 접근해봅시다.


첫번째 레이저는 스킵하겠습니다 (지워지는 조각이 없습니다.)

두번째 레이저입니다.

‘(((’ 괄호가 3개가 있네요 + 3개 카운트해주겠습니다.

세번째 레이저입니다.

똑같이 닫는 ‘)’가 없으므로 3개 더 카운트해주면 됩니다 (총 6개)

그 후 닫히는 괄호 하나 해서 + 1

네번째 레이저입니다.

그리고 ‘((’ + ‘(’ 으로 + 3개 ( 10개)

여기서도 괄호가 하나 더 닫히므로 + 1 해주겠습니다.

다섯번째 레이저입니다.

닫히는 괄호를 제외하면 맨 앞 ‘((’ 두 개만 있습니다 + 2개 해주겠습니다. (총 13개)

그리고 닫히는 괄호 2개 해서 + 2개 해주겠습니다. (총 15개)

그리고 마지막으로 여섯번째 레이저는 조각 2개

총 17개가 됩니다!

이를 문제 코드로 볼까요?

문제 코드

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

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

    stack<char> bracket_stack;  // 괄호를 저장하는 스택
    int total_pieces = 0;       // 총 잘려진 쇠막대기의 조각 수
    string input;               // 입력 문자열

    cin >> input;

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '(') {
            bracket_stack.push(input[i]);  // 여는 괄호를 스택에 추가
        } else { // input[i] == ')'
            if (input[i - 1] == '(') {
                // 레이저인 경우
                bracket_stack.pop();      // 레이저의 여는 괄호 제거
                total_pieces += bracket_stack.size();  // 현재 스택 크기만큼 조각 추가
            } else {
                // 쇠막대기의 끝인 경우
                bracket_stack.pop();      // 쇠막대기의 끝을 처리
                total_pieces++;           // 하나의 조각 추가
            }
        }
    }

    cout << total_pieces << "\n";

    return 0;
}

문제 코드에서 주석을 통해 설명을 보충했습니다.

해당 문제는 O(N)으로 해결할 수 있겠죠?
감사합니다!