[BOJ] 백준 10799번 쇠막대기 - JAVA 자바 풀이

접근법

1. 여는 괄호 '(' 일 때는 막대나 레이저 상관 없이 스택에 push 합니다.
2. 닫는 괄호 ')' 일 때 두 가지 경우의 수가 있습니다. 레이저 또는 막대의 끝을 나타낼 수 있습니다.
   • 레이저라면 현재 스택 사이즈 (아직 끝나지 않은 막대의 수)를 더합니다.
   • 막대의 끝이라면 잘린 막대가 하나 늘어난 것이므로 1을 더합니다. (아래 그림에서 빨간색으로 표시)

 

Java 코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayDeque<Character> stack = new ArrayDeque<>();
        String line = br.readLine();

        int sum = 0;
        for (int i=0; i<line.length(); i++) {
            char c = line.charAt(i);

            if(c==')') {
                if(line.charAt(i-1) == '(') { // 레이저일 때
                    stack.pop();
                    sum += stack.size();
                }
                else { // 막대의 끝일 때
                    stack.pop();
                    sum++;
                }
            } else {
                stack.push('(');
            }
        }
        System.out.println(sum);
    }
}

 

문제 링크

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