[백준] JAVA 자바 : 스택 수열 (1874번)

---

스택 수열을 만드는 문제다.
처음에는 문제를 이해하기 되게 어려웠는데… 나도 다른 분들 블로그를 보고 겨우 이해했다.

무슨 내용이냐면, 첫 줄에 n을 입력한 후 나는 이제 수열을 이룰 숫자 num을 n번 입력받을 거다.,
num을 입력하면, 스택에는 1부터 차례대로 1, 2, …, num까지 입력이 되어야 한다.
그리고 맨 스택의 맨 위의 요소를 pop하면 내가 입력한 num이 도출되어야 한다.

즉 내가 4를 입력하면 스택에는 1, 2, 3, 4가 저장된 후 4가 pop되어 출력되고 스택에는 1, 2, 3이 남게 된다.
이후 내가 3을 입력하면 스택에 추가로 저장할 필요가 없으니 바로 pop되어 3이 출력되고 스택에는 1, 2가 남게 된다.
이후 내가 6을 입력하면 스택에는 1, 2가 입력되어 있고, 나는 이미 3과 4를 저장했으니 이제 5와 6을 저장하여 스택에는 1, 2, 5, 6이 저장되고 pop하여 6이 출력되며 스택에는 1, 2, 5가 남는다.

이렇게 n번 진행이 가능하다면 push와 pop 연산을 +와 -로 나타내면 되고, 불가능하다면 NO를 출력하는 문제이다.

… 대충 무슨 문제인지 알겠지? 이해가 안 된다면 죄송합니다.

 

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

public class StackSequence_1874 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int top=0;
        int num;
        boolean pass = true; // 이게 false가 되면 NO를 출력하게 할 거임
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i=0; i<n; i++) {
            num = scan.nextInt();
            if (top < num) { // 기존에 넣었던 수들 보다 더 큰 수가 들어오면
                for (int j=top+1; j<=num; j++) { // 그 수까지 스택에 넣은 후
                    stack.push(j);
                    sb.append("+\n");
                }
                top = num; // 우리가 넣은 수 중 가장 큰 수?를 기록해준다.
            }
            if (stack.peek() == num) { // 맨 마지막 수가 우리가 도출해야 할 수가 맞는지 확인
                stack.pop(); // 맞다면 pop
                sb.append("-\n");
            } else { // 아니라면 스택 수열 불가.
                pass = false;
            }
        }
        
        System.out.print(pass ? sb : "NO");
    }

}

NO를 출력하는 조건만 잘 설정해 준다면 아마 쉽게 풀 수 있을 것이다.

 

 

작성일자: 2023-08-30