[BOJ][JAVA] 1874 스택 수열

1874 스택 수열

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

풀이 방법

처음엔 말을 이해를 못했었는데 그냥 간단한 스택 문제였다.
스택에는 1부터 n까지의 정수가 순서대로 들어가는데 주어진 입력값에 맞춰 스택에 있는 정수를 빼면 되는 문제이다.

문제의 포인트는
1. push는 어떻게 할 것인가?
2. 불가능 처리는 어떻게 할 것인가?
이다.

1. push는 먼저 현재 스택이 비어있거나 입력값이 스택의 Top보다 큰 경우에만 진행한다. 그리고 중요한 것이 high라는 현재 스택에 push했었던 최댓값을 저장하는 변수를 선언하여 그 이후 값부터 push하도록 해야 한다. 아니면 이미 push했던 값도 중복으로 들어갈 수 있다.
2. 불가능 처리는 스택에 정상적으로 넣고 나면 간단히 해결되는데 스택의 Top 값이랑 입력값이 일치하지 않으면 불가능한 것으로 보면 된다.

예를 들어 3 2 1 5 4 라는 입력값이 들어왔다고 하자.
처음엔 high가 0이기에 첫 입력값인 3을 보고 1부터 3까지 스택에 넣게 된다.
이후 스택의 Top인 3과 입력값인 3이 일치하는지 확인 후 pop한다.
그 다음 입력값인 2는 현재 스택이 비어있지도 않고 스택의 Top보다 크지 않으므로 push는 하지 않는다.
이후 일치하는지 확인한 후 pop한다.
그렇게 1까지 pop한 후 다음 입력값인 5를 보면 현재 스택이 비어있으므로 high(3)의 다음 값(4)부터 입력값(5)까지 스택에 push한다. 그리고 반복하면
+ + + - - - + + - - 이런 결과가 나오게 된다.

소스 코드

import java.util.Scanner;
import java.util.Stack;

public class Problem_1874 {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        Stack<Integer> stack = new Stack<>();
        int high = 0;

        int n = scanner.nextInt();
        scanner.nextLine();

        for(int i = 0; i < n; i++) {
            int number = scanner.nextInt();
            scanner.nextLine();

            if(stack.empty()) {
                for(int j = high + 1; j <= number; j++) {
                    sb.append("+\n");
                    stack.push(j);
                }
                high = number;
            }
            else if(number > stack.peek()) {
                for(int j = high + 1; j <= number; j++) {
                    sb.append("+\n");
                    stack.push(j);
                }
                high = number;
            }

            if(number != stack.peek()) {
                sb = new StringBuilder("NO");
                break;
            }

            sb.append("-\n");
            stack.pop();
        }

        scanner.close();

        System.out.println(sb);
    }
}