[백준] 1874 - 스택수열

 

처음에는, 이미 스택으로 들어온 값을 check해주는 배열을 통해서 조건을 검사하는 방식으로 코드를 구현했다. 결과는 시간초과..

그래서 1 ~ n까지 들어간 수를 start pointer로 가리키는 방식을 적용했다. 이렇게 하면 check 배열이 별도로 필요가 없어진다.

또한 start pointer보다 작을 경우에만 stack에 넣고 큰 경우에는 pop이 가능한지 check 하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int start = 1;

        while(n-- > 0) {

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

            if(start <= inp) {
                for(int i = start; i<=inp; i++) {
                    stack.add(i);
                    sb.append("+\n");
                }
                start = inp + 1;
            }

            if(stack.pop() == inp) {
                sb.append("-\n");
            } else {
                System.out.println("NO");
                return;
            }
        }
        System.out.println(sb);
    }
}