오름차순 수열

스택

스택을 이용한 오름차순 수열을 만드는 알고리즘입니다.

스택은 기본적으로 LIFO(후입선출)방식 입니다.

즉, 데이터를 저장하고나서, pop(꺼내는 명령어)를 하면 최근에 저장한 데이터를 꺼내는 방식입니다.

이를 활용하여 다양한 알고리즘을 작성할 수 있는데, 그중 스택으로 오름차순 수열을 만드는 알고리즘을 작성해보겠습니다.

코드예시 [ 백준 1874 문제 ]

package Silver;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int A = Integer.parseInt(st.nextToken());
        int[] numberset = new int[A];
        Stack<Integer> resultData = new Stack<>();
        for (int i = 0; i < A; i++) {
            st = new StringTokenizer(in.readLine());
            int data = Integer.parseInt(st.nextToken());
            numberset[i] = data;
        }
        int nn = 1;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A; i++) {
            int C = numberset[i];
            if(nn <= C) {
                while (nn <= C) {
                    resultData.push(nn);
                    sb.append("+\n");
                    nn++;
                }
                resultData.pop();
                sb.append("-\n");
            } else {
                if (!resultData.isEmpty() && resultData.peek() == C){
                    resultData.pop();
                    sb.append("-\n");
                } else {
                    System.out.println("NO");
                    in.close();
                    return;
                }
            }
        }
        System.out.println(sb);
        in.close();
    }
}