백준/1874번/Java - 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

num의 범위 =1부터 n까지의 자연수

arr[i]를 스택에서 꺼내기 위해서는 스택에 num (arr[i]보다 작은 수)부터 arr[i]까지 오름차순으로 집어넣어야 함.

스택의 최상단이 arr[i]가 되면 stack에서 pop한다 (= 배열로 늘어놓는다).

다시 arr[i+1]을 스택에서 꺼내기 위해서는 arr[i+1]까지 오름차순으로 집어넣음.

스택의 최상단이 arr[i+1]이 되면 스택에서 pop.

arr[i+1]이 스택의 최상단보다 작으면 "NO"

꺼내야하는 수가 3이고 스택이 위에서부터 4,3 순으로 쌓여있을 때, 3을 꺼내 배열에 늘어놓기 위해서는 먼저 4를 pop해야 한다.

하지만 이 경우 3을 꺼내기 위해 앞서 꺼내버린 4는 배열에 다시 늘어놓을 방법이 사라진다.

 (이미 스택에서 제거되었기 때문. 문제의 조건에 따르면

같은 수는 두번 나오지 않는다.)

* 처음에는 BufferedWriter를 사용하고 NO 조건에서는 sysout한 뒤, System.exit(0);로 종료시켰는데 자꾸 오답처리가 되었다.

인프런 강의를 참고하여 StringBuffer를 사용하고, boolean 플래그를 사용하여 판별하였더니 통과하였다.

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> stack = new Stack<>();
        StringBuffer sb = new StringBuffer();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        boolean result = true;

        int num = 1; //스택에 들어갈 수
        for(int i=0; i<n; i++) {
            int target = arr[i];
            if(num <= target) {
                while(num <= target) {
                	//꺼내야하는 수가 스택에 쌓일 때까지 스택을 쌓아준다.
                    stack.push(num++); //push 후 ++
                    sb.append("+\n");
                }
                //while문 종료 : num == target인 상황
                //꺼내야하는 수가 스택의 맨 위까지 쌓였으므로 pop
                stack.pop(); 
                sb.append("-\n");
            }
            else { 
            	// 스택에 들어갈 차례가 된 수가 스택에서 꺼낼 수보다 큰 상황.
                // = 스택에 수를 쌓을 필요가 없다.
                if(stack.peek() > target) {
                    //스택의 최상단 수가 꺼내야하는 수보다 큰 상황
                    // => 해당 수를 꺼내게 되면 배열에 늘어놓을 수 없음.
                    result = false;
                    break;
                } else { 
                	//ex : 스택 : 3, 2, 1 
                    //     꺼내야하는 수(target) : 3 
                    //     스택에 들어갈 수(num) : 5
                    stack.pop();
                    sb.append("-\n");
                }
            }
        }
        if(result) {
            System.out.println(sb);
        } else {
            System.out.println("NO");
        }
        br.close();
    }
}