[BOJ-JAVA] 10799번: 쇠막대기

문제

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

10799번: 쇠막대기

다음과 같이 괄호로 이루어진 문장이 주어질 때 막대기의 개수를 세는 문제이다.

• 괄호는 레이저를 나타낸다.
  • 괄호 안에 포함된 가장 안쪽 괄호가 레이저가 된다.
• 모든 막대기는 괄호를 포함한다.
• 막대기에 대해 가장 안쪽 괄호 기준으로 나누었을 때 막대기 개수를 구해야한다.

 

문제 풀이

보통의 괄호를 이용한 문제는 stack을 이용해 해결할 수 있다.

• "("가 나올 경우 stack에 push
• ")"가 나올 경우 stack에서 pop

다음과 같은 규칙을 찾을 수 있다.

• 단순히 하나의 괄호 쌍 "()"에 대해서는 개수를 세지 않는다.
  • 레이저이기 때문
• 하나의 레이저를 지나갈 때 잘라진 막대기 개수를 센다.
  • 잘라진 막대기 개수는 stack의 size, 즉 (의 개수와 같다. (레이저 괄호 제외)
• 연속으로 ")"가 나올 때는 막대기 개수가 1만 증가한다.

 

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for(int i=0; i<line.length(); i++) {
            if(line.charAt(i) == '(') {
                stack.push('(');
            }
            else{
                if(line.charAt(i-1) == ')') {
                    count++;
                }
                else if(stack.size() > 1) {
                    count += stack.size()-1;
                }
                stack.pop();
            }
        }
        System.out.println(count);
    }
}