[Algorithm] 쇠막대기

Jong Min ·2025년 4월 8일

algorithm

Algorithm

목록 보기

21/30

🧤 쇠막대기 (백준 10799)

쇠막대기 - 백준 10799

📌 문제 설명

여러 개의 쇠막대기를 레이저로 절단하려고 한다.
쇠막대기와 레이저는 아래와 같은 방식으로 표현된다:

( : 쇠막대기의 시작
() : 레이저
) : 쇠막대기의 끝

레이저는 쇠막대기를 위에서 수직으로 절단하며, 절단된 쇠막대기 조각의 총 개수를 구하는 문제이다.

🎯 입력 조건

한 줄의 괄호 문자열이 주어진다.
괄호의 길이는 최대 100,000을 넘지 않음

📝 예제 입력 및 출력

입력

()(((()())(())()))(())

출력

💡 해결 방법

스택을 사용해서 문제를 해결할 수 있다.
문자열을 왼쪽부터 하나씩 순회하면서,

'('를 만나면 스택에 push
')'를 만나면 직전 문자가 '('인지 확인:
- 레이저라면 → 방금 넣은 '('을 pop하고, 현재 스택에 쌓여 있는 개수만큼 잘리므로 result += stack.size()
- 쇠막대기의 끝이라면 → pop 하고 result += 1

✅ 코드

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine(); // 입력 문자열
        Stack<Character> stack = new Stack<>();

        int result = 0; // 잘려진 조각의 총 개수

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('('); // 여는 괄호는 무조건 push
            } else if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 레이저인 경우
                    stack.pop(); // 레이저 앞 괄호 제거
                    result += stack.size(); // 현재 스택에 쌓인 쇠막대기 수만큼 조각 추가
                } else {
                    // 쇠막대기 끝인 경우
                    stack.pop(); // 하나의 쇠막대기가 끝났으므로 pop
                    result += 1; // 끝난 막대는 무조건 하나의 조각 추가
                }
            }
        }

        System.out.print(result);
    }
}