[백준_Stack]1874번_스택 수열

스택을 응용한 문제라고 할 수 있는 스택 수열!!

1이상 n이하의 정수가 하나씩 순서대로 입력이 되고, 이렇게 입력되어 생성된 수열(ex 4 3 2 1) 을 1부터 다시 입력된다고 생각할 때, Stack을 이용해 표현할 수 있는지 없는지, 있다면 push를 + , pop을 - 로 출력하여 전체 순서를 출력하고, 없다면 NO를 출력하면 되는 문제!!

바로 코드를 보도록 하자!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Al1874 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        boolean[] flag = new boolean[testCase + 1];
        Stack<Integer> stack = new Stack<>();
        StringBuilder builder = new StringBuilder();
 
        int[] check = new int[testCase];
        for (int i = 0; i < testCase; i++) {
            check[i] = Integer.parseInt(br.readLine());
        }
 
        stack.push(0);
        for (int i = 0; i < check.length; i++) {
            while (true) {
                int val = stack.peek();
                if (val < check[i]) {
                    if(flag[val+1]) {
                        while (flag[val + 1]) val++;
                    }
                    stack.push(val+1);
                    builder.append("+\n");
                } else if (val > check[i]) {
                    System.out.println("NO");
                    return;
                } else if (val == check[i]) {
                    int temp = stack.pop();
                    builder.append("-\n");
                    flag[temp] = true;
                    break;
                }
            }
        }
        System.out.println(builder.toString());
    }
}

먼저 입력되는 값을 배열로 받아 저장하고, 배열 길이 만큼 for문을 돌리면서 풀면 된다!

만약 stack의 top에 위치한 값이 배열에 저장된 값보다 작다면?

그 값까지 +1 을 해준다!!

만약 같다면?!

pop을 하여, 그 값을 출력하면 된다!!

이때 1 ~ n 까지 모든 숫자는 단 한번만 사용되기 때문에 이미 사용된 숫자인지 아닌지 여부를 확인해야 한다

나는 boolean[] flag 를 선언하여, 방문할 경우 true 값을 주어 확인하였다!

그리고 만약 stack의 top에 위치한 값이 배열에 저장된 구해야 하는 값보다 크다면?

해당 수열은 stack을 이용하여 만들 수 없으므로 "NO"를 출력한다.

왜냐하면 1 ~ n 까지 모든 숫자가 사용되어야 하며, stack의 top 값이 배열의 다음 값보다 클 경우,

stack을 pop하지 않는 이상, 배열의 다음 값을 구할 수 가 없기 때문이다.

그렇다고 pop을 하는 순간 수열의 다른 위치에 있어야 할 값이 출력되는 것이기 때문에 pop을 할 수도 없다.

그렇기 때문에 NO!!

이제는 또 어떤 문제를 풀까~