[백준/JAVA] 1874

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

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));

        StringBuilder sb = new StringBuilder();
        // N 입력
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        int lastVal = 0;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            // 스택의 top이 입력하려는 값보다 작을 경우 수행 stack.peek()
            if (lastVal < num) {
                // 스택에 원하는 값까지 입력
                for (int j = lastVal; j < num; j++) {
                    stack.push(j+1);
                    sb.append("+ ");
                }
                lastVal = num;
            } else if (stack.peek() != num) {
                bw.write("NO");
                bw.flush();
                return;
            }
            // 스택의 push가 완료되면 top이 입력 값과 같아지고 pop수행
            stack.pop();
            sb.append("- ");
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

알고리즘 동작 원리는 다음과 같다.

• 입력받은 수 까지 push한다.
• push가 끝나면 마지막 lastVal 값은 입력받은 값이 되므로 pop을 진행해준다.
  (단, push가 끝났을 때 lastVal과 num의 값이 다르면 이는 잘못된 문제이므로 "NO"를 출력한다.)
• 이를 N번 반복한다.

자료구조의 Stack의 push(), pop(), peek() 메소드를 사용하였다.
첫 시작또한 stack.peek()을 사용하려 했으나, 초기값이 없으므로 lastVal = 0 으로 시작했다.