[백준][Java] 10799 - 쇠막대기

2025. 1. 15. 01:45·알고리즘/문제풀이 :백준
목차
  1. 📌문제 설명
  2. 💡생각
  3. 🔥풀이
바킹독강의 문제 중 스택의 활용(수식의 괄호 쌍) 응용 문제를 풀면서 어려웠던 부분과 생각하지 못했던 부분에 대해서 설명할려고 한다!!

📌문제 설명

백준 10799 쇠막대기

여러 개의 쇠 막대기를 레이저로 절단하려고 한다. 

쇠막대기와 레이저의 배치 조건

  • 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
  • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
  • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

백준 10799의 예시 문제

() : 레이저를 아래로 발사하는 구간이다.

(....) : 막대의 역할을 하고 있고 사이에는 막대가 있을 수 있고, 레이저를 발사할 수 있다.

 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조건의 총 개수를 구하는 프로그램을 작성해라!!

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

💡생각

처음에 문제를 보고 두가지 경우를 나눠야 겠다고 생각을 했다.

  1. 괄호가 막대기인 경우
  2. 괄호가 레이저인 경우

괄호가 레이저인 경우 = 여는 괄호와 닫힌 괄호가 바로 붙어있을 때로 생각했다. 이후 괄호가 막대기인 경우를 생각해봤지만 도저히 생각이 안났다. 

  • 열린 괄호를 만났을 때 스택에 push한다.
  • 닫힌 괄호를 만났을 때 스택에 있는 여는 괄호를 pop한다. 
  • 여기서 pop할 때 막대기인지 레이저인지 구분하는 방법을 생각하지 못했다. 

그래서 고민 끝에 바킹독 문제집의 답지 코드를 보고 이해를 할 수 있었다!!!

🔥풀이

문제를 스택의 크기를 이용해서 풀수 있었다.

 

생각을 해보자.

  • 만약 스택에 여는 괄호가 3개가 들어있는 상태에서 닫힌 괄호가 들어오면 어떻게 될까??
    • 만약 앞에 여는 괄호가 있었다면 닫힌 괄호는 레이저를 발사하는 위치로 인식되야 할 것이다.
    • 스택에 들어있는 여는 괄호는 사이에 레이저가 있기 때문에 막대기의 시작점으로 인식이 되야할 것이다.
    • 이때 생긴 레이저는 아직 막대기의 끝을 만나지 않은 스택에 있는 모든 막대들을 자를 수 있는 레이저가 될 것이다!!
    • 그래서 스택에 있는 막대기를 레이저에 의해 잘라지는 막대가 됨. -> 결과 값에 여는괄호 한개를 제외한 스택 사이즈를 더해준다. +2가 더해질 것이다.
그럼 막대기의 끝은 어떻게 해야할까??

내가 이 부분을 너무 어렵게 생각한 것 같다.

닫힌 괄호 바로 앞에 여는 괄호가 없다면 막대기의 끝으로 인식된다고 생각하면 된다. -> 이걸 해결하는걸 너무 어렵게 생각한 것 같다!!

예시 문제 : ((())())
 그림이 아직 많이 미숙하다.... 잘 설명할 수 있도록 하는 방법을 더 생각해봐야 겠다!!

 

최종적으로 작성한 코드다!!

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack<Character> stack = new Stack<>();
        String str = br.readLine();

        int strLength = str.length();
        int result = 0;
        for(int i = 0;i<strLength;i++){
            if(str.charAt(i) == '('){
                stack.push(str.charAt(i));
            }else
            {
                if(str.charAt(i-1) == '('){
                    stack.pop();
                    result = result + stack.size();
                }
                else
                {
                    stack.pop();
                    result = result + 1;
                }
            }
        }
        System.out.println(result);
    }
}

'알고리즘 > 문제풀이 :백준' 카테고리의 다른 글

[백준][C++] 토너먼트  (0) 2025.04.29
[백준][c++] 1024-수열의 합  (0) 2025.04.13
[백준][c++] 1002-터렛  (0) 2025.04.13
[백준][JAVA] 2493 탑  (1) 2025.01.20
[백준][JAVA] 2579 계단 오르기  (0) 2025.01.06
  1. 📌문제 설명
  2. 💡생각
  3. 🔥풀이
'알고리즘/문제풀이 :백준' 카테고리의 다른 글
  • [백준][c++] 1024-수열의 합
  • [백준][c++] 1002-터렛
  • [백준][JAVA] 2493 탑
  • [백준][JAVA] 2579 계단 오르기
각쿄
각쿄
  • 각쿄
    개발일기
    각쿄
  • 전체
    오늘
    어제
    • 분류 전체보기 (24)
      • 알고리즘 (13)
        • 문제풀이 : 프로그래머스 (0)
        • 문제풀이 :백준 (13)
        • 알고리즘 개념 (0)
      • 자료구조 (2)
      • 기초 (0)
        • 운영체제 (0)
        • 디자인패턴 (0)
        • 웹 (0)
        • 컴퓨터 네트워크 (0)
      • Spring (0)
      • IT이슈 (0)
      • 자바(Java) (5)
      • 에러(Error) (2)
        • Mysql (1)
      • 활동 (0)
        • 혼공학습단13기 - 혼자 공부하는 컴퓨터구조 운영.. (0)
      • 기능 구현! (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Stack
    mysql
    혼공학습단
    이분탐색
    스택
    백준
    Java
    다이나믹 프로그래밍
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
각쿄
[백준][Java] 10799 - 쇠막대기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.