설명

• LIFO(Last In First Out) 특성을 갖고 있는 스택의 기능을 이용하여 문제를 풀이한다.
  • 자료를 넣는 입구와 자료를 뽑는 입구가 같다.
• push와 pop을 통해 임의의 수열을 만들 수 있는지 판단하며, 해당 수열을 오름차순을 지켜야 한다.

예제를 살펴보면 수열의 첫번째 입력값이 '4'이므로 정수를 스택에 push 한다.

int start = 0; 	// 정수에 넣기 시작하는 값

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

if(value > start) {
	for(int i = start + 1; i <= value; i++){
    	stack.push(i);
    }
    start = value;	// 이전에 어디까지 입력 받았는지 알기 위해 start를 value 값으로 초기화한다.
}

스택의 맨 위 원소가 첫번재 수열인 4라면 pop 하고, 같지 않다면 수열을 만족하지 못하므로 NO를 출력한다.

else if(stack.peek() != value){
	System.out.println("NO");
    return;
} else if(stack.peek() == value) {
	// value 값까지 push하면 pop을 한다.
	stack.pop();
}

코드

package Algorithm.P1874;

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

public class P1874 {
    static int n;
    static Stack<Integer> stack = new Stack();
    static int start = 0;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P1874/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());

        while (n != 0) {
            int value = Integer. parseInt(br.readLine());
            if (value > start) {
                for (int i = start + 1; i <= value; i++) {
                    stack.push(i);
                    sb.append('+').append('\n');
                }
                start = value;
            }
            else if (stack.peek() != value) {
                System.out.println("NO");
                return;
            } else if (stack.peek() == value) {
                stack.pop();
                sb.append('-').append('\n');
            }
            n--;
        }
        System.out.println(sb);
    }
}

Reference

• https://st-lab.tistory.com/182