풀이 아이디어

순열 순서대로 입력을 받으면서 확인을 한다.
오름차순으로 순열의 값을 집어넣는데 다음에 들어갈 숫자를 currentNum
스택의 맨위의 숫자값을 topNum
예제 입력을 받고 현재 순열상 pop해야하는 숫자값을 inputNum이라하면

1. 스택이 비어있는 경우
   currentNum이 inputNum만큼 같아질 때까지 때까지 push를 한다.
   for(int j=currentNum;j<=inputNum;j++)
   그 뒤에 currentNum = inputNum+1;로 갱신해준다.
2. 스택이 채워져있는 경우
   크게 3가지 케이스로 나눌 수 있다.
   • topNum > inputNum
     : 나머지 순열 상 절대 될 수 없는 경우이므로 "NO"를 출력하고 프로그램을 종료한다.
   • topNum == inputNum
     : stack.pop()을 하고 "-\n"를 추가한다.
   • topNum < inputNum
     : currentNum==inputNum만큼이 될때까지 숫자를 푸쉬하며
     currentNum을 1씩 추가해준다.

풀이 코드

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

public class _1874 {
    public static void main(String[] args) throws IOException{
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int currentNum = 1; // 다음에 들어갈 숫자
        int inputNum; // 입력받은 수
        int topNum; // 스택 맨위 값

        for(int i=1;i<=n;i++){
            inputNum = Integer.parseInt(br.readLine());

            // 스택이 비어있는 경우
            if(stack.isEmpty()){
                for(int j=currentNum;j<=inputNum;j++){
                    stack.push(j);
                    sb.append("+\n");
                }
                currentNum = inputNum+1;
            } 
            // 스택이 채워져 있는 경우
            if(!stack.isEmpty()){
                topNum = stack.peek();

                // peek > inputNum인 경우 NO
                if(topNum > inputNum){
                    System.out.println("NO");
                    return;
                }
                // peek == inputNum인 경우 pop
                else if(topNum == inputNum){
                    stack.pop();
                    sb.append("-\n");
                }
                // peek < inputNum인 경우 push
                else if(topNum < inputNum){
                    for(int j=currentNum;j<=inputNum;j++){
                        stack.push(j);
                        sb.append("+\n");
                    }
                    currentNum = inputNum+1;
                    stack.pop();
                    sb.append("-\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}