백준 1874: 스택 수열과 마지막으로 넣은 수

백준 1874번 스택 수열은 1부터 N까지 순서대로 스택에 넣으면서 주어진 수열을 만들 수 있는지 확인하는 문제입니다. 넣는 연산은 +, 꺼내는 연산은 -로 기록합니다.

lastVal과 스택의 맨 위는 다릅니다

lastVal에는 지금까지 스택에 넣은 가장 큰 수를 저장했습니다. 다음으로 꺼낼 수 num이 더 크면 아직 넣지 않은 수부터 num까지 차례대로 넣습니다. 그러면 스택 맨 위가 num이 되니 하나를 꺼냅니다.

반대로 num을 이미 넣은 적이 있다면 스택 맨 위를 확인합니다. 맨 위가 num이 아니면 다른 수를 먼저 꺼내야 하므로 목표 수열을 만들 수 없습니다. 이때는 NO를 출력하고 끝냅니다.

처음에는 시작할 때도 peek()를 쓰려고 했습니다. 하지만 빈 스택에는 확인할 값이 없어서 아직 아무 수도 넣지 않았다는 뜻으로 lastVal = 0에서 시작했습니다.

당시 코드

아래 코드는 연산 뒤에 줄바꿈 대신 공백을 붙입니다. 문제의 출력 형식은 연산을 한 줄에 하나씩 쓰도록 되어 있습니다. 그래서 다시 제출한다면 sb.append("+\n"), sb.append("-\n")처럼 줄바꿈을 넣어야 합니다.

Java

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

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

        StringBuilder sb = new StringBuilder();
        // N 입력
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        int lastVal = 0;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            // 스택의 top이 입력하려는 값보다 작을 경우 수행 stack.peek()
            if (lastVal < num) {
                // 스택에 원하는 값까지 입력
                for (int j = lastVal; j < num; j++) {
                    stack.push(j+1);
                    sb.append("+ ");
                }
                lastVal = num;
            } else if (stack.peek() != num) {
                bw.write("NO");
                bw.flush();
                return;
            }
            // 스택의 push가 완료되면 top이 입력 값과 같아지고 pop수행
            stack.pop();
            sb.append("- ");
        }
        bw.write(sb.toString());
        bw.flush();
    }
}