[Java] 백준 쇠막대기

1. 문제분석

괄호가 닫힌다면 레이저가 존재하는 것이고 자르게 된다.

여기서 봐야할 점은 스택을 하나씩 넣어보면서 계산한다는 점이다. 처음부터 다 넣고 pop을 해서 보는게 아니다.

 

만약 ')'라면 레이저거나 쇠막대기의 끝이거나가 된다.

먼저 레이저면 쇠막대기를 자르는 것이다. 그렇게 되면 위의 그림처럼 전체적인 쇠막대기를 자르는 것이다.

반대로 괄호가 전부 닫혀 마지막 쇠막대기가 된 상태를 보자.

마지막에 레이저가 존재하지 않지만 자르고 남은 쇠막대기가 1개 남는다.

 

이를 통해 문제를 해결 하면 된다.

2. 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        Stack<Character>stack = new Stack<>();
        int result = 0;

        for(int i = 0; i<input.length(); i++){
            if(input.charAt(i) == '('){
                stack.push('(');
                continue;
            }
            if(input.charAt(i) == ')'){
                stack.pop();

                if(input.charAt(i - 1) == '('){
                    //전에가 '('라면 레이저로 자른다.
                    result += stack.size();
                }
                else{
                    //마지막으로 자르면 막대기가 1개가 남는다.
                    result++;
                }
            }
        }
        bw.write(result + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

먼저 '('가 나오면 스택에 넣어준다.

그리고 ')'가 나오는 경우 2가지를 확인해야 한다. 

 

1. 아직 남은 막대기가 존재하는지?

2. 이게 막대기의 마지막 인지?

 

그 부분을 if문으로 구현했다. 만약 아직 쇠막대기가 남았으면 그 만큼 개수를 더해주고 없다면 마지막 1개를 더해준다.

3. 마무리

사이드 프로젝트를 2개 진행하면서 알고리즘까지 할려고 하니 너무 바쁘다.

스택을 처음부터 다 넣는다라고 생각하지말고 차근차근 생각해보자.