[JAVA] 백준 10799번 【쇠막대기】

---

이 문제는 Stack 클래스를 이용해서 해결하였다.

 

포인트는, 나눠진 쇠 막대기를 어떤 조건일 때, 어떤 값을 더해야하는지 파악하는 것이다.

 

차근차근 하나씩 그려보면, 바로 이해가 된다.

 

 

---

 

 

위와 같은 상황이 있다고 가정할때,

 

'(' 가 있으면 스택에 '(' 를 계속 push 해주고 ')' 가 나올때 pop을 해주고 나서 조건을 따져봐야 한다.

 

---

 

 

 

첫 번째, ')' 를 만났다. 바로 이전 문자가 '(' 이므로 레이저임을 알 수 있다.

 

만약 ')' 를 만났을 때, 이전 문자가 ')' 라면 레이저가 아닐 것이다.

 

아무튼, 레이저가 발사되고, 남은 두개의 '(' 의 끝은 알 수 없지만,

 

확실한 건 현재 스택의 사이즈 만큼의 조각이 생긴다는 사실이다.

 

즉, result = result + stack.size(); 가 성립한다.

 

---

 

또 ')'를 만났고, 현재 3개의 '(' 가 있다.

 

역시, 3개의 쇠 막대기의 끝은 알 수 없지만, 레이져가 발사되면서 stack 사이즈만큼의 조각이 추가 됨을 알 수 있다.

 

따라서 result = result + stack.size(); 가 성립한다.

 

---

 

 

위 경우도 마찬가지로  result = result + stack.size(); 가 성립한다.

 

 

---

 

위 경우는, ')' 를 만났지만, 이전 문자가 ')' 이므로 레이저가 아니고 쇠막대기의 끝임을 알 수 있다.

 

따라서 위, 빨간색 표시와 같이, 조각이 1개만 추가가 된다.

 

따라서 result = result +1 ; 임을 알 수 있다.

 

---

 

위 경우도, 쇠막대기의 끝이기 때문에 빨간색 조각이 하나 추가 될 것이다.

 

따라서 result = result +1 ; 이 될 것이다.

 

 

---

 

 

마지막 경우, 역시 쇠막대기의 끝을 의미하고, 조각의 갯수가 +1이 될 것이다.

 

 

 

즉.

 

1. '(' 인 경우 스택에 계속 쌓는다.

 

2. ')' 를 만난경우

     2-1. 이전 문자가 '(' 라면 레이져임을 알 수 있고, 결과값에 stack.size() 를 더한다.

     2-2. 이전 문자가 ')' 라면 레이져는 아니고, 쇠막대기의 끝이 하나 생성되므로 결과값에 1을 더한다.

 

위 두가지 규칙을 구현하면 된다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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('(');
            }
            if (input.charAt(i) == ')') {
                if (input.charAt(i - 1) == '(') {
                    stack.pop();
                    result += stack.size();
                } else {
                    stack.pop();
                    result += 1;
                }
            }
        }
        System.out.println(result);
    }
}