백준_1874 스택 수열 (스택)

 

 

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

public class BJ_1874 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int i, temp, num, popNum;

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        num=1;

        for(i=0; i<n; i++) {
            temp = Integer.parseInt(br.readLine());

            if(temp > num-1) {
                while(temp > num-1) {
                    stack.push(num++);
                    sb.append('+').append('\n');
                }
                stack.pop();
                sb.append('-').append('\n');
            }

            else {
                if(temp < stack.pop()) {
                    sb = new StringBuilder();
                    sb.append("NO");
                    break;
                }
                else { // 이 경우는 pop한 수가 temp랑 같을 경우. 작을 경우는 이론상 말이 안됨
                    sb.append('-').append('\n');
                }
            }
        }

        System.out.println(sb);
    }
}

 

안쪽 else에서 작을 경우가 있을 수 없는 이유.

바깥 else문에 들어왔다는 것은 temp가 오름차수 수보다 작다는 것.

안쪽 else에서는 stack의  top이 temp보다 작지 않다는 것.

stack의 top이 n이라고 한다면 이미 n보다 크고 오름차수보다 작은 수들은 입력됐다가 pop됐다는 것인데,

문제의 입력 값은 중복되지 않기에 오름차수 수 보다 작고 n보다 큰 수가 temp일 수는 없다.
따라서 안쪽 else문은 결국 temp == top 인 경우만 해당한다.

 

1874번: 스택 수열