백준 10799번) 쇠막대기 java

 

분석

---

문제에 있는 조건들을 잘 활용해야한다.

1. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.

-> 쇠막대기를 표현하는 괄호가 서로 겹치지 않는다는 것을 의미한다.

 

2. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

-> 쇠막대기는 적어도 두개 이상의 조각으로 잘려진다.

 

3.  레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

-> 쇠막대기의 끝을 나타내는 괄호가 혼돈 방지 , 적어도 두 이상의 조각으로 잘려짐을 의미

 

문제에 주어진 조건을 활용하면 쉽게 풀 수 있다.

 

먼저 예시를 살펴보면 

레이저가 처음으로 막대기를 자르면 1번 영역에서 3개의 조각이 생긴다. 

2번 영역에서 자르게 되면 다시 3개의 조각이 생긴다. 

3번 영역에서는 되면 밑에 두개는 잘리지 않고 맨 위 막대기만 1조각이 더 생긴다.

 

여기서 패턴을 발견할 수 있는데 , '(' 가 입력이 되면 레이저가 들어올때 생기는 조각이 하나씩 늘어나는 거라고 생각할 수 있다.

그리고 쇠막대기가 끝났을때는 가장 짧은 쇠막대기 조각이 한 조각 더 생기는 것이다.

 

이런식으로 쭉 이어가면 

3+3+1+3+1+2+2+2 = 17

결과적으로 17 조각이 나온다.

 

스택을 이용하여 다시 설명해보면 ,

1. '(' 이 입력이 되면 스택에 push를 해준다.

2. 레이저가 입력되면 스택 사이즈만큼 조각수를 더해준다.

3. 쇠막대기가 끝나면 조각수를 +1 해주고 해당 막대기에 해당하는 쇠막대기를 pop해준다.

 

소스코드

---

 

import org.w3c.dom.ls.LSOutput;

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        Stack<Character> s = new Stack<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int result = 0;

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

}