[JAVA]BOJ 10799, 쇠막대기

처음엔.. 어떻게해야하지? 고민했는데.. 1.파이프일때는 스택에 넣고 2.레이저일때는 스택에 넣지 않는다. 그리고 3.파이프를 스택에 넣을때 파이프의 개수를 증가시킨다. 4.레이저를 만났을때 파이프의 개수를 스택에 비례해 증가시킨다. 규칙은 이렇다.

메모장에 적은 알고리즘..

위에 코드 짤 알고리즘을 타이핑으로 쳐봤다. ((( -> 이게 스택이다. 마지막줄에 - 는 스택이 비었음을 의미한다.

더하기 부분에서 0 + 3 = 3 이거는 cnt가 0인데 스택에 ((( <- 파이프를 3개 넣으면서 각각 1씩 더해졌음을 의미한다. 그리고 두번째 줄의 3 + 3 = 6 은 레이저를 만나서 각 파이프별로 +1을 해준것이다. 스택에 파이프가 3개 있으니 사실상 스택사이즈를 더하는 것과 같다. 너무 대충적어서 포스팅에 포함할까 말까 고민했는데.. 그냥 넣었다. 코드에 주석설명도 붙였으니 괜찮겟지

---

아래는 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class BOJ10799 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        String str;
        int i, cnt = 0;

        str = br.readLine();

        for(i=0;i<str.length();i++){
            if(str.charAt(i) == '('){
                if(str.charAt(i+1) == ')') { // 레이저를 확인하기
                    cnt += stack.size();
                    i++; // 레이저의 ')'인경우 지나치려고 증가시킴
                }
                else {
                    stack.add(str.charAt(i));
                    cnt++;
                }
            }
            else
                stack.pop();
        }
        System.out.println(cnt);
    }
}