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

바킹독강의 문제 중 스택의 활용(수식의 괄호 쌍) 응용 문제를 풀면서 어려웠던 부분과 생각하지 못했던 부분에 대해서 설명할려고 한다!!

📌문제 설명

백준 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);
    }
}