[JAVA] 백준 1874번 : 스택 수열

https://www.acmicpc.net/problem/1874
이 문제를 이해하는 데에 시간이 많이 소요됐었다. 하지만, 문제를 이해하고 난 후에는 쉽게 풀 수 있었다.

문제 설명

입력이 8이면, '1,2,3,4,5,6,7,8'의 숫자가 있는 것이다. 이 숫자들을 스택에 넣고 빼 문제에서 입력받은 숫자인 '4,3,6,8,7,5,2,1'을 만드는 것이다. 즉, 다음과 같은 과정을 따르면 된다.

1. 스택에 숫자를 1씩 증가시켜 계속 넣음
2. 스택의 peek 값이 입력된 숫자와 같으면 pop을 해 줌

초반에는 for문을 이용하여 i값을 넣고 현재 입력된 값과 비교해 주었다. i가 1씩 증가시키는 로직은 같지만, 입력된 값과 같을 때 까지 스택에 넣어야 하는데 i를 넣고 같지 않으면 바로 다음 입력값으로 넘어가 버리기 때문에 이렇게 하면 안된다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int currentNum = 1; //현재 stack에 넣어야 할 숫자
        boolean possible = true; //수열을 만들 수 있는지 여부

        for (int i = 1; i <= n; i++) { //i값을 가지고 원래 있는 수열과 비교
            int num = Integer.parseInt(br.readLine()); //숫자를 입력받음
            while (currentNum <= num) { //넣어야 하는 숫자가 입력받은 숫자보다 같아질 까지
                stack.push(currentNum); //스택에 숫자를 넣음
                sb.append("+").append("\n"); //+추가
                currentNum++;
            }
            if (stack.peek() == num) { //스택의 최상단 요소가 입력받은 숫자와 같으면
                stack.pop(); //스택에서 제거
                sb.append("-").append("\n");
            } else {
                possible = false;
                break;
            }
        }
        if (possible) {
            System.out.println(sb); //출력
        } else {
            System.out.println("NO");
        }
        br.close();
    }
}