백준 1874 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

---

코드

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));
        Stack stack=new Stack();

        int n=Integer.parseInt(br.readLine());
        int[] sequence=new int[n];

        for(int i=0; i<n; i++)
            sequence[i] = Integer.parseInt(br.readLine());

        char[] result=new char[n*2];
        int resultIndex=0;

        int temp=0;
        int i=1;
        for(int index=0; index<n; index++){
            if(temp<sequence[index]) {
                while (sequence[index] != i) {
                    stack.push(i++);
                    result[resultIndex++] = '+';
                }
                stack.push(i++);
                result[resultIndex++]='+';
            }

            if((int)stack.pop()!=sequence[index]){
                System.out.println("NO");
                return;
            }
            result[resultIndex++]='-';
            temp=sequence[index];
        }

        for(char a:result)
            System.out.println(a);
    }
}

---

해결 과정

1. 우선 예제를 보고 1부터 직접 진행해보면서 "NO"가 출력되는 조건을 찾아보았다. 주어진 수열에서 가장 큰 수가 나오기 전까지는 무조건 주어진 수열과 동일하게 Stack을 이용해서 출력할 수 있다. 그러나 그 이후에는 오름차순으로 push를 했기 때문에 pop을 했을 때 무조건 내림차순으로 나올 것이다. 따라서 주어진 수열에서 가장 큰 수 다음으로 오는 수열은 무조건 내림차순으로 정렬되어 있어야 한다.
   
   이것을 깨닫고 주어진 수열이 "NO"가 아니라는 가정 하에 맞게 출력되도록 '+'와 '-'를 넣기 위한 char형의 배열(사이즈는 pop의 수와 push의 수가 각각 수열의 크기와 같기 때문에 수열의 크기*2)을 만들고, 오름차순으로 주어지는 자연수보다 주어진 수열에서 현재 출력해야 하는 수가 크다면 push, 작다면 pop을 해서 pop을 할 때마다 현재 출력해야 하는 수와 일치하는지 판단했다.
2. 😁