백준 1874_스택 수열_JAVA

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

1874번: 스택 수열

 

 

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

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());
        int[] arr = new int[N]; // 우리가 만들어야하는 배열

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

        Stack<Integer> stack = new Stack<>();
        int num = 1;  // 1부터 stack에 넣으면서 증가시켜줄 in 생성
        StringBuffer sb = new StringBuffer(); // +,- 의 답을 저장할 곳
        boolean result = true; // 중간에 만들어 질 수 없는 배열이라 끊겼는지 확인

        for (int i=0; i<N; i++) {
            if (arr[i] >= num) {
                while (arr[i] >= num) {
                    stack.push(num++); // num을 stack에 push하고 증가시켜줌
                    sb.append("+\n");
                }
                stack.pop(); // 만들어야 하는 배열이랑 같아졌으니 stack에서 pop
                sb.append("-\n");
            }
            else {
                int n = stack.pop();
                if (n>arr[i]) {
                    // 현재 스택의 가장 위에 있는 값이 구해야하는 수열의 값보다 크다? 바로 NO 출력
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    // 이 구문으로 왔다는 건 pop한 것이랑 arr[i]랑 같은 것
                    sb.append("-\n");
                }
            }
        }

        if (result) {
            System.out.print(sb.toString());
        }
    }
}

 

회고

- Stack의 원리를 알고 있어서 푸는 방법은 어느정도 이해할 수 있었다.

- 코드 짜는 것이 생각보다 쉽지 않았다.