문제 이해

숫자 n이 주어질 것이다.

모든 단계에서 1부터 n까지 순차적으로 Stack에 Push되거나, stack에 저장된 값이 pop 될 수 있다.

총 n개의 숫자가 주어질 것이다. 만약 정상적인 단계를 거쳐서(즉, 1 ~ n까지 순차적으로 Push하거나 Pop하면서) n개의 숫자 순서를 출력할 수 있다면 Push할 때 +, Pop할 때 -를 출력하여 전체 과정을 출력한다.

그리고 n개의 숫자 순서를 표현할 수 없다면 NO를 출력하면 된다.

---

문제 풀이

Stack은 이미 JAVA나 Python에 구현되어 있으므로 직접 해보면 되는 문제이다.

만약 arr 값과 다르다면 계속해서 Push 시키고, Stack의 가장 위에 존재하는 값과 arr 값이 같다면 Stack에서 Pop시키고 arr의 다음 index값과 비교해보면 되는 것이다.

중요한 것은 Stack에 데이터를 모두 쌓으면 Stack이 빌 때 까지 Pop시켜 남은 arr 구간과 일치하는지를 확인하는 과정이 필요하다는 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	public static void main(String[] args) {
		int N = sc.nextInt();
		Stack<Integer> stack = new Stack<>();
		
		int[] arr = new int[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		int index = 0;
		int num = 1;
	
		while(true) {
			if(num > N) break;
            /* 
             * index >= N인 경우는 고려하지 않아도 된다.
             * 만약 index = N이라는 것은 arr를 끝까지 Search했다는 의미이다
             * 이 말은 stack에 모든 값이 Push되어 있어야만 가능한 조건이다
             * 따라서, num > N인 조건만 확인하면 index >= N인 조건은
             * 자동으로 처리되는 조건인 것이다.
             */
			
			if(stack.isEmpty()) {
            // 스택이 비었다면 Push만 가능하다. 따라서 현재 숫자인
            // num을 Push하고 num을 1 증가시킨다
            // Push 과정을 거치므로 +를 출력한다.
				stack.push(num);
				num++;
				sb.append("+\n");
				continue;
			}
			
			if(stack.peek()==arr[index]) {
            // Stack의 맨 위 값과 arr의 값이 일치한다.
            // 따라서, Pop을 시키면 arr값 출력이 가능하다
            // Search할 arr의 index를 1 증가시키고, Pop시켰으므로 -를 출력한다
				stack.pop();
				sb.append("-\n");
				index++;
			}
			else {
            // Stack의 맨 위 값과 arr 값이 불일치한다.
            // 따라서 Stack에 num을 Push하고 num을 1 증가시킨다
            // Push 과정이므로 +를 출력한다
				stack.push(num);
				num++;
				sb.append("+\n");
			}
		}
		
		while(!stack.isEmpty()) {
        // Stack이 빌 때 까지 Pop시킨다
			if(stack.pop()!=arr[index]) {
            // 만약 Pop한 값과 arr[index]가 다르다면 원래는 Push 과정을 
            // 거쳐야 한다.
            // 하지만, 위쪽의 while문에서 Push할 숫자는 모두 소모하였다.
            // 즉, Push가 불가능한데 Push 과정이 필요하므로 출력이 불가능한
            // Case인 것이다
				System.out.println("NO");
				return;
			}
			sb.append("-\n");
			index++;
		}
		
        // 여기까지 코드가 왔다는 것은 return이 없다는 의미이다.
        // 따라서 sb에 저장된 Pop & Push 과정을 출력만 하면 된다
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과