[BOJ_10799 | Stack] 쇠막대기

풀이

스택을 이용해서 풀어야하는 문제였다. 물론 반복문을 이용해서 풀 수도 있겠지만, 스택을 활용하면 문제풀이가 훨씬 용이해진다.

간단히 정리해보자면, 스택은 FIFO(First in First out)을 특징으로 하는 자료구조이다.

말 그래도, 먼저 넣은 데이터가 먼저 나오게 하는 구조인 것이다.

이를 이용해서 쇠막대기를 레이저로 자를때 한번에 몇개씩 자르는지를 쉽게 구할 수 있다.

*출처 Wikipedia

원리는 다음과 같다.

'(' 가 나오면 스택에 '(' 를 집어넣고 막대기의 개수를 하나 추가한다.

예를 들어 '((((' 이런식인 경우 계속 스택에 쌓기만 하는 것이다.

막대기의 개수는 4개가 될 것이다.

그 다음이 중요한데, 만약 ')' 가 나오는 경우 "막대기의 개수를 하나 줄이고" 막대기의 개수만큼 

총 sum에 더해주는 것이다.

"(())의 경우 쇠막대기 하나를 둘로 자르는 입력값이다.

이때 ((를 처리하면서 막대기를 두개 만들어주고, )를 처리하면서 막대기를 하나 줄이고 그 개수만큼 더해주고

다시 한번 )를 처리하면서 막대기를 또 하나 줄이고 더해주는 것이다.

마지막으로 주의해야 할 점은 ')' 가 연속으로 나오는 경우이다.

')가 연속으로 나오는 경우에는 막대기의 개수를 더해주는 것이 아니라 1만큼만 더해주어야 한다.

'()'가 나와야 절단하는 것이기 때문에 연속적인 '))'의 경우는 그냥 막대기가 끝난다는 의미이기 때문이다.

예를 들어 ((()))의 경우가 나왔다면, 실제로 절단은 1번만 일어나고, 나머지 2번에 대해서는 그냥

막대기 길이가 짧아서 끝난다는 것이기 때문에 그냥 그 막대기 1개만큼만 Sum에 더해주면 된다. 

소스 코드

import java.util.*;
public class BOJ_10799 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        Stack<Character> stack = new Stack<Character>();
        String inStr = input.next();

        int stick = 0; int sum = 0;
        char before = '.';

        for(int i=0;i< inStr.length();i++){
            char c = inStr.charAt(i);
            if(c == '('){
                stick ++;
                stack.push(c);
            }else if(c == ')'){
                stick--;
                stack.pop();
                if(before == ')') sum += 1;
                else sum += stick;
            }else{ System.out.println("Input Mismatch Error Occur!"); break; }
            before = c;
        }
        System.out.println(sum);
    }
}