[백준] 10799 쇠막대기 - Java

문제

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

 

---

 

문제 개요

여러 개의 쇠막대기를 위에서 아래로 레이저로 절단하는 문제입니다. 레이저와 쇠막대기는 괄호 표현으로 주어지며, 레이저는 인접한 ‘( )’로 나타납니다. 각 쇠막대기는 ‘(’로 시작하여 ‘)’로 끝나고, 레이저가 쇠막대기를 절단하면서 조각의 총 개수를 계산하는 것이 목표입니다.

 

접근 방법

1. 스택을 이용한 괄호 쌍 확인: 쇠막대기의 끝과 레이저를 구분하기 위해 스택 자료구조를 사용합니다.
2. 레이저와 막대기 구분:
   • ‘(’는 막대기 시작을 나타내므로 스택에 푸시합니다.
   • ‘)’를 만났을 때, 이전 문자가 ‘(’라면 레이저입니다. 레이저는 현재 스택의 크기만큼 막대기를 절단하므로, 스택에 남은 막대기의 수만큼 조각 수를 더합니다.
   • 만약 이전 문자가 ‘)’라면 막대기의 끝을 나타내므로, 조각을 하나 더해줍니다.
   •  

해결 과정

1. 문자열을 처음부터 끝까지 순회하면서 각 문자가 여는 괄호 ‘(’인지, 닫는 괄호 ‘)’인지 판별합니다.
2. 레이저일 경우:
   • 닫는 괄호 ‘)’의 바로 앞이 여는 괄호 ‘(’이면, 레이저이므로 스택에 남은 막대기의 개수만큼 조각 수를 증가시킵니다.
3. 막대기의 끝일 경우:
   • 닫는 괄호가 연속으로 나오는 경우이므로, 현재 막대기 조각의 끝을 의미하여 조각 하나를 추가합니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");  // 괄호 문자열 입력받기
        Stack<String> stack = new Stack<>();  // 괄호 상태 확인을 위한 스택
        int answer = 0;

        for(int i = 0; i < arr.length; i++) {
            if(arr[i].equals("(")) {  // 여는 괄호일 경우
                stack.push(arr[i]);
            } else {  // 닫는 괄호일 경우
                stack.pop();  // 스택에서 여는 괄호 제거
                if(arr[i - 1].equals("(")) {  // 레이저일 경우
                    answer += stack.size();  // 스택 크기만큼 조각 추가
                } else {  // 막대기 끝일 경우
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
}