[Baekjoon] 10799번: 쇠막대기 - Java

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

10799번: 쇠막대기

문제 설명

일련의 괄호 문자열이 주어지고 잘려진 쇠막대기 조각의 총 개수를 구하면 된다.

풀이 방법

괄호 문제의 대표적인 해결 방법인 스택을 활용하면 된다.

먼저 여는 괄호인 경우는 일단 스택에 넣는다. 그러다 닫는 괄호를 만나면 그 때 레이저인지 쇠막대인지를 판단한다.

 

만약 레이저라면 이때까지 넣어뒀던 쇠막대를 모두 자르게 되므로 결과값에 스택의 사이즈만큼 더해준다.

만약 쇠막대라면 그 쇠막대의 길이가 거기까지인 것이므로 결과값에 마지막에 남은 1만 더해준다.

핵심 코드는 다음과 같다.

for (int i = 0; i < expression.length(); i++) {
    if (expression.charAt(i) == '(')
        stack.push(expression.charAt(i));
    else {
        stack.pop();
        if (expression.charAt(i - 1) == '(')
            ans += stack.size();
        else
            ans += 1;
    }
}

전체 코드는 다음과 같다.

package baekjoon.stack;

import java.io.*;
import java.util.Stack;

public class BOJ10799 {

    static Stack<Character> stack = new Stack<>();
    static int ans;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String expression = br.readLine();

            for (int i = 0; i < expression.length(); i++) {
                if (expression.charAt(i) == '(')
                    stack.push(expression.charAt(i));
                else {
                    stack.pop();
                    if (expression.charAt(i - 1) == '(')
                        ans += stack.size();
                    else
                        ans += 1;
                }
            }

            System.out.println(ans);
        }
    }
}