1874. 스택 수열 (자바, Java)

처음에 상당히 난해하게 느꼈던 문제. 문제가 뭐냐면, 중간에 내려가게 되면 peek값은 내려가지만, 그 후에 다시 올라가는 경우 기준값은 그전에 스택에 쌓였던 값 중 최대값이 된다. 따라서 최대값만 기억해주면 크게 어렵지는 않다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Stack <Integer>stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		int max = 0;
		
		for (int i=0; i<n; i++) {
			int k = Integer.parseInt(br.readLine()); // 입력받은 숫자
			
			if (max<k) {
				for (int j=max+1; j<=k; j++) {
					stack.push(j);
					sb.append("+\n");
				}
				max = k;
			}
			
			if (k==stack.peek()) {
				stack.pop();
				sb.append("-\n");
			} else {
				System.out.println("NO");
				System.exit(0);
			}
		}
		System.out.println(sb);
	}

}