[백준1874번] 스택 수열

문제

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

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

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

8
4
3
6
8
7
5
2
1

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2

5
1
2
5
3
4

예제 출력 2

NO

나의 풀이

이 문제를 처음 읽고는 문제자체가 잘 이해가 가지않았었다. 그래서 예제를 봐가면서 종이에 끄적여보다보니 문제를 이해할 수 있었다. 간단히 설명하자면 1부터 n까지 차례대로 스택에 넣으면서 입력으로 주어지는 순서대로의 수열을 만들 수 있나 없나를 판단하라는 문제인데 예제 1번을 보면 n이 8이고 주어지는 수열이 [4,3,6,8,7,5,2,1]이다. 그럼 이제 순서대로 스택에 1부터 넣어보면서 생각해보자.

1 : [1]
2 : [1,2]
3 : [1,2,3]
4 : [1,2,3,4]

자, 4까지 넣었다면 수열이 스택이 위와 같이 쌓여있을 것이다. 여기서 주어지는 수열이 [4,3,6...]인 것을 보면 4까지 쌓인 스택에서 4를 pop하고 3을 pop하면 스택에는 [1,2]가 남게되고 수열 [4,3]까지는 만들 수 있는 상황이 된다. 그럼 더 진행해보자.

5 : [1,2,5]
6 : [1,2,5,6]  => 6이 pop된다.
7 : [1,2,5,7]
8 : [1,2,5,7,8] => 이제는 8부터 차례대로 pop이 되면 수열을 완성시킬 수 있다.

이렇게 문제를 이해하고 나면 풀기 수월해진다.

우선 List로 1부터 n까지 순서대로 담을 stack과 push와 pop의 결과를 담을 result를 만들어 놓고 입력으로 주어지는 수열을 int형 배열에 담았다.

그리고나서 for문으로 1부터 n까지 모두 push를 하는 과정을 만들고 그 안에서 그때마다 입력으로 주어지는 수열과 비교를 해가며 pop을 해준다. 또 중요한 점은 while문으로 stack이 비어있지않고 top(가장 최근에 들어온 값)이 수열의 값과 같으면 이때도 pop을 해준다. 또한 수열이 담긴 배열을 따로 인덱스를 저장할 변수를 만들어두고 수열이 하나씩 일치하여 pop이 될때마다 인덱스 값도 증가를 시켜주었다.

이렇게 for문이 모두 돌고나면 stack이 비어있을수도 있고 비어있지 않을수도 있다. 여기서 비어있다면 모든 수열이 완성되었으므로 result를 출력해주고 그렇지 않다면 "NO"를 출력해 줌으로써 문제를 해결할 수 있다.

이 문제는 처음에 문제를 이해하는데 조금 어려움이 있었지 막상 문제를 해결하는데는 큰 어려움이 없었다.

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 1874번 스택 수열
 */
public class Baekjoon1874 {
    static List<Integer> stack = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Character> result = new ArrayList<>();

        int n = sc.nextInt();

        int[] seq = new int[n+1];

        for (int i=1; i<=n; i++) {
            seq[i] = sc.nextInt();
        }

        int seqIndex = 1;
        for (int i=1; i<=n; i++) {
            // 우선 i를 push하고 본다.
            push(i);
            result.add('+');

            // i와 현재 인덱스의 수열과 같으면 pop
            if (i == seq[seqIndex]) {
                pop();
                result.add('-');
                seqIndex++;
            }

            // stack이 비어있지않고 top값이 수열과 같으면 pop
            while (!stack.isEmpty() && top() == seq[seqIndex]) {
                pop();
                result.add('-');
                seqIndex++;
            }
        }

        // stack이 비어있다면 수열 완성
        if (stack.isEmpty()) {
            for (Character op: result) {
                System.out.println(op);
            }
        } else System.out.println("NO");


    }

    private static void push(int num) {
        stack.add(num);
    }

    private static void pop() {
        if (stack.isEmpty()) {
            System.out.println("Error");
            System.exit(-1);
        } else {
            stack.remove(stack.size()-1);
        }
    }

    private static int top() {
        if (stack.isEmpty()) {
            System.out.println("Error");
            System.exit(-1);
        }
        return stack.get(stack.size()-1);
    }
}