[백준] 1874번 스택수열

 

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

1) 스택의 peek가 비교항(s)과 같아 질 수 있는지를 중심으로 판단

peek == s (o)

peek >  s : 절대 같아질 수 없음

peek <  s : max > s이면 같아질 수 없고, max < s 이면 같아질 수 있음

 

2) 1 ~ n 까지 모두 넣어야 하고 스택에서 pop연산을 수행하는 순간 만들고자하는 수열에 값이 추가됨.

3) 메모리 128MB 이하

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {

		// 1. n 입력받기
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
			
		// 1-1. 변수 초기화
		StringBuilder sb = new StringBuilder(); 
		String result ="";
			
		Stack<Integer> stack = new Stack<Integer>();
		int max  = 0; // 스택에 넣은 최댓값
		int peek = 0; // 스택 최상단 값
		
		// 2. 수열 만들기
		while(n-- > 0) {
			int s = scan.nextInt();
			
			if(s == peek) {	 
				stack.pop(); sb.append("-\n");
				
			}else if(s > peek && s > max) { // stack이 비어있지 않음
				while(max != s) {
						stack.push(++max); sb.append("+\n");
				}
				stack.pop(); sb.append("-\n");
		
			}else { // s > peek, s >= max or s < peek, s > max
				result = "NO";
				break;
			}
			
			if(stack.empty())
				peek = 0;
			else
				peek = stack.peek();
			
		}
		scan.close();
				
		if(!result.equals("NO")) 
			result = sb.toString().substring(0, sb.length());
		
		// 3. 출력
		System.out.println(result);
					
	}//main

}