[백준] 스택 수열

• 문제 링크 : https://www.acmicpc.net/problem/1874

• 이 문제는 1부터 n사이의 정수 수열이 주어졌을 때, 그 수열을 1부터 n까지 차례로
  스택에 push, pop함으로서 만들수 있는지를 검증하는 문제이다.
  
  예를 들면,
  4 3 6 8 7 5 2 1 인 수열이 주어졌을 때,
  

1. 4를 꺼내야 하므로 1~4까지 스택에 push -> [1,2,3,4]
2. 4를 바로꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1,2,3] / 수열: [4]
3. 스택의 마지막 수가 3이므로 pop -> 스택: [1,2] / 수열: [4,3]
4. 6을 꺼내야 하므로 5~6까지 스택에 push -> [1,2,5,6]
5. 6을 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1,2,5] / 수열: [4,3,6]
6. 8을 꺼내야 하므로 7~8까지 스택에 push -> [1,2,5,7,8]
7. 8를 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1,2,5,7] / 수열: [4,3,6,8]
8. 7을 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1,2,5] / 수열: [4,3,6,8,7]
9. 5을 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1,2] / 수열: [4,3,6,8,7,5]
10. 2을 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [1] / 수열: [4,3,6,8,7,2]
11. 1을 바로 꺼내 수열에 넣을 수 있으므로 pop -> 스택: [] / 수열: [4,3,6,8,7] -> 완성!
    
    요약하면,
    먼저 수열에 들어가야 하는 수가 현재 스택에 없다면 스택에 작은 수 부터 넣고 pop을
    해주면 되고,
    수열에 들어가야 하는 수가 현재 스택에 있다면 현재 꺼낼 수 있는지를 검사하고
    꺼낼 수 있다면 꺼내고, 꺼낼 수 없다면 실패이다(그 수를 꺼내려면 먼저 현재 꺼낼 수 있는 수를 꺼내야 하는데, 그렇게 되면 수열의 순서가 망가지게 된다).

public class Q1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());

        int index = 0; //현재 마지막으로 스택에 들어간 수 

        for (int i = 0; i < N; i++) {

            int num = Integer.parseInt(br.readLine());

            if (index < num) { //목표 숫자가 스택에 없다면
                for (int j = index+1; j <= num; j++) { //숫자를 목표 숫자까지 push
                    stack.push(j);
                    sb.append("+\n");
                }
                index = num; //마지막으로 스택에 들어간 수를 초기화
            } else if (stack.peek() != num) { //목표 숫자가 스택에 있지만, 바로 꺼낼 수 없을때
                System.out.println("No");
            }

            stack.pop(); //위의 모든 경우에서 목표 숫자를 스택에서 바로 꺼낼 수 있으므로 
            sb.append("-\n");



        }
        System.out.println(sb);
    }
}