[백준] 1874번 - 스택 수열 (Java)(△)

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

1874번: 스택 수열

 

<풀이>

1. 1~n 까지의 자연수를 스택에 집어 넣는다.

2. 그 n까지의 자연수들을 스택에 넣었다 뺐다 하면서 입력값으로 주어진 수열을 만들 수 있는지 확인한다.

3. 오름차순으로 증가시키면서 집어 넣는데 push 때는 '+', pop은 '-'을 출력한다. 불가능하면 'NO'을 출력한다.

 

<Hint>

 

<구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Stack;
import java.util.Scanner;

public class Main {
    static int N, L;
    static int A[];

	void Solve() {
        Stack <Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int num = 1;
        // 수열기준으로 반복함
        for (int i=0; i<N; i++) {
            int su = A[i];
            //1. 현재 수열의 수 >= 오름차순 자연수일 경우
            if (su >= num) {
                //값이 같아질 때까지 push한다.
                while (su >= num) {
                    stack.push(num++);
                    sb.append("+\n");
                }
                // 같아지면 그 수는 pop함
                stack.pop();
                sb.append("-\n");
            } else {
                //2. 현재 수열의 수 < 오름차순 자연수일 경우
                int top = stack.peek();
                // 스택의 마지막 수가 수열보다 크면 진행이 불가능
                if (top > su) {
                    System.out.println("NO");
                    return;
                } else {
                    stack.pop();
                    sb.append("-\n");
                }
            }
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        //StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        //st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}