백준 10799번 쇠막대기: C언어 풀이

백준 10799 쇠막대기 문제의 C언어 해설입니다.
스택 자료구조 대신 이전에 등장한 문자를 저장하여 문제를 해결한 방법을 설명합니다.

전략

조각을 세는 방법

작업대에서 쇠 막대기를 자르는 기계가 있다.
편의상 막대의 길이는 무한하다고 가정해보자.
작업자에게 내릴 수 있는 명령은 다음 4가지이다.

1. 작업대에 막대를 놓는다.
2. 작업대에서 막대를 치운다.
3. 작업대에 놓인 막대를 자른다. 잘린 왼쪽 조각을 조각 통에 넣는다.

사람마다 다를 수 있겠지만, 이렇게 생각하면 상황이 좀 더 명확해진다.
작업대 위 막대 수를 aligned_sticks, 조각 통 속 막대 수를 cut_sticks라고 하자.

작업대에 막대를 놓으면 aligned_stics가 하나 추가된다.
작업대에서 막대를 치우면 aligned_sticks가 하나 감소한다.
작업대에 놓인 막대를 자르면 cut_sticks가 aligned_sticks만큼 증가한다.

이제 명령을 차례대로 수행하면서 cut_sticks를 계산하면 된다.

막대와 레이저가 기호를 공유하는 문제

위 상황에서 1번은 (, 2번은 (), 3번은 )로 표현된다.
괄호 표현식을 단순히 한 글자씩 읽으면서 처리할 수가 없다. 막대와 레이저가 기호를 공유하기 때문이다.
글자 (가 나왔을때 막대를 놓으라는 명령인지, 혹은 막대를 자르는 명령의 일부인지 구분할 수 있어야 한다.

그래서 직전에 나왔던 괄호가 무엇이었는지를 따로 저장해주기로 했다.

먼저 여는 괄호 (를 무조건 1번 명령, 즉 막대를 놓는 명령으로 처리한다.

닫는 괄호 )가 나오면 직전에 나왔던 괄호를 확인한다.

• 닫는 괄호 )라면 막대를 자르는 명령이다.
• 여는 괄호 (라면 막대를 자르는 명령의 일부이다.

자르기 전에 이전에 한 실수를 되돌려야한다.
우리는 여는 괄호를 무조건 막대를 놓는 명령으로 해석했다. 사실은 자르는 명령의 일부였었다.
막대를 놓는 명령은 aligned_sticks를 1만큼 더하니까, 1을 다시 빼주면 간단하게 되돌릴 수 있다.

코드

#include <stdio.h>

int main(void)
{
    int aligned_sticks = 0;
    int cut_sticks = 0;

    char prev_char;
    char c;
    while ((c = getchar()) != '\n')
    {
        switch (c)
        {
            case '(':
                aligned_sticks++;
                break;
            case ')':
                // Stick ended, thus not aligned 
                if (prev_char == ')')
                {
                    aligned_sticks--;
                    cut_sticks++;
                }
                // Activate laser 
                else 
                {
                    aligned_sticks--;
                    cut_sticks += aligned_sticks;
                }
                break;
        }
        prev_char = c;
    }

    printf("%d\n", cut_sticks);
}