[BOJ/Java] 쇠막대기 (10799)

쇠막대기 (10799)

1. 문제 분석

문제 개요

• 쇠막대기가 여러 개의 조각으로 나누어진 모양이 주어진다.
• 쇠막대기와 그 위의 막대기들을 스택을 이용해 잘라진 조각의 개수를 세는 문제다.

입력 형식

• 첫 줄에 쇠막대기의 모양을 나타내는 문자열이 주어진다. 문자열은 괄호로만 구성된다.

출력 형식

• 잘라진 쇠막대기의 조각 수를 출력한다.

2. 알고리즘 종류

이 문제는 스택을 이용한 괄호 분석 문제로, 쇠막대기를 정확히 잘라내기 위해 스택을 활용해 괄호의 위치를 분석하는 방식으로 해결할 수 있다.

3. 주요 부분 및 코드 작성 방법

1. 스택 사용

• 여는 괄호 (를 만나면 스택에 추가하고, 닫는 괄호 )를 만나면 스택에서 제거한다.
• 닫는 괄호가 여는 괄호 바로 뒤에 나오면 레이저로 판단하고, 스택의 크기만큼 조각 수를 추가한다.
• 연속된 닫는 괄호는 막대기의 끝부분으로 판단하고, 그 개수만큼 조각 수를 증가시킨다.

2. 현재 상태와 스택의 최상단 비교

• 닫는 괄호가 나올 때 스택의 크기와 연속된 괄호의 조합을 확인하여 조각 수를 계산한다.

4. 코드 설명

메인 함수 (main)

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성
        String s = sc.nextLine(); // 입력된 문자열을 읽어옴
        System.out.println(solve(s)); // 문자열을 해결하여 조각 수를 출력
    }

    public static int solve(String s) {
        Stack<Character> stack = new Stack<>(); // 문자형 스택 생성
        int cnt = 0; // 조각 수를 저장할 변수

        for (int i = 0; i < s.length(); i++) { // 문자열을 한 문자씩 처리
            char c = s.charAt(i); // 현재 문자

            if (c == '(') {
                stack.push(c); // 여는 괄호는 스택에 추가
            } else if (c == ')') {
                stack.pop(); // 닫는 괄호는 스택에서 제거

                // 닫는 괄호가 여는 괄호 바로 뒤에 오면 레이저로 판단
                if (s.charAt(i - 1) == '(') {
                    cnt += stack.size(); // 스택의 크기만큼 조각 수 추가
                } else {
                    cnt++; // 연속된 닫는 괄호는 조각 수를 증가시킴
                }
            }
        }

        return cnt; // 총 조각 수 반환
    }
}

5. 전체 코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성
        String s = sc.nextLine(); // 입력된 문자열을 읽어옴
        System.out.println(solve(s)); // 문자열을 해결하여 조각 수를 출력
    }

    public static int solve(String s) {
        Stack<Character> stack = new Stack<>(); // 문자형 스택 생성
        int cnt = 0; // 조각 수를 저장할 변수

        for (int i = 0; i < s.length(); i++) { // 문자열을 한 문자씩 처리
            char c = s.charAt(i); // 현재 문자

            if (c == '(') {
                stack.push(c); // 여는 괄호는 스택에 추가
            } else if (c == ')') {
                stack.pop(); // 닫는 괄호는 스택에서 제거

                // 닫는 괄호가 여는 괄호 바로 뒤에 오면 레이저로 판단
                if (s.charAt(i - 1) == '(') {
                    cnt += stack.size(); // 스택의 크기만큼 조각 수 추가
                } else {
                    cnt++; // 연속된 닫는 괄호는 조각 수를 증가시킴
                }
            }
        }

        return cnt; // 총 조각 수 반환
    }
}