[백준][실버][스택] 1874 스택 수열

1874 스택 수열

1. 문제

문제

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

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

입력

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

출력

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

입/출력 예제

입력
8
4
3
6
8
7
5
2
1

출력
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

2. 풀기 전 문제 파악

다른 알고리즘 문제와 마찬가지고 문제를 이해하는게 어렵다..
아래의 그림을 보면서 문제를 이해해보자.

1. 배열의 값이 4일 때, 1 2 3 4를 스택에 담고 배열의 값인 4를 꺼낸다.
2. 다음 배열의 값은 3인데 스택에는 1 2 3이 담겨있고 3을 바로 꺼낼 수 있으므로 꺼낸다.
3. 다음 배열의 값은 6, 스택에는 1 2가 담겨있고 우리는 이전에 스택에 4까지 담았으므로 5부터 담을 수 있다.
   • 5 6을 스택에 담고 6을 꺼낸다.
4. 입력받은 수열이 끝날 때까지 위를 반복한다.

• 두번째 입력 예제인 1 2 5 3 4를 보면
  1. 1과 2인 경우 각각 1, 2를 스택에 담았다 뺀다
  2. 3번째 5인 경우 3, 4, 5를 스택에 담은 후 5를 빼준다.
  3. 4번째 값이 3인데 스택에는 3과 4가 남아있다. 3을 빼내기 위해서 4도 빼야 한다. -> 3을 뺀다.
  4. 근데 마지막 값이 4... 우리는 이미 2번에서 5를 꺼내기 위해서 3, 4, 5를 스택에 담았다 뺐으므로 더 이상 진행할 수 없다.

➡️ 스택에 담을 때의 값을 가지고 있다가 비교해야 한다.
- 우리가 마지막으로 스택에 넣었던 값보다 배열의 값이 크면 스택에 담는다(마지막으로 스택에 넣었던 값 ~ 배열의 값) + 꺼낸다.
- 스택에 넣었던 값(5)보다 배열의 값이 작을 때, 배열의 값(4)이 스택에서 꺼낸 값(1)보다 크면 종료
- 아니면 스택에서 꺼낸다.(3의 경우)

3. 문제 풀기

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

// https://www.acmicpc.net/problem/1874
public class Main {
    private static int N;
    private static int[] NUMS;
    private static StringBuffer sb = new StringBuffer();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        NUMS = new int[N];
        for (int i = 0; i < N; i++) {
            NUMS[i] = Integer.parseInt(br.readLine());
        }

        solution();
        System.out.println(sb.toString());

        br.close();
    }

    private static void solution() {
        Stack<Integer> stack = new Stack();

        int cursor = 1;

        for (int i = 0; i < NUMS.length; i++) {
            int num = NUMS[i];
            // 배열에서 읽은 값이 커서보다 크면 스택에 넣는다.(다 넣고 제일 위의 수는 꺼낸다.)
            if (num >= cursor) {
                while (num >= cursor) {
                    stack.push(cursor++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            // 작으면 그냥 꺼내면 되는데 배열에서 읽은 수가 스택에서 꺼낸 수보다 크면 더 이상 수열을 만들 수 없음 -> NO 리턴
            } else {
                int popNum = stack.pop();

                if (popNum > num) {
                    sb.delete(0, sb.length());
                    sb.append("NO");
                    return;
                } else {
                    sb.append("-\n");
                }
            }
        }
    }
}