[BOJ] 1874번 스택수열 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

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

        int idx = 0;
        for (int i = 1; i <= N; i++) {
            stack.push(i);
            sb.append("+\n");

            while (!stack.isEmpty() && stack.peek() == target[idx]) {
                stack.pop();
                idx++;
                sb.append("-\n");
            }
        }

        if (!stack.isEmpty()) {
            System.out.println("NO");
            return;
        }
        System.out.println(sb);
    }
}

📄 해설

접근

• 문제에 나와있듯, 스택을 사용하여 해결하는 문제이다.
• 스택에 넣는 순서는 오름차순이라고 했으므로, 1부터 N까지 스택에 넣고 빼면서 해당 수열을 만들 수 있는지 확인하면 된다.
• 만들려고하는 수열을 배열에 저장하고, 이를 스택의 탑과 비교한다.
• 1 부터 N 까지 처리를 마쳤음에도 스택이 비어있지 않다면 해당 수열을 만들 수 없다.

과정

• 길이가 N인 수열을 길이가 N인 배열 target 에 저장한다.

• 1부터 N까지 숫자를 증가시키면서 아래 과정을 반복한다.

  1. 현재 숫자를 스택에 넣고 + 를 출력한다.
  2. 스택의 탑에 있는 숫자가 target[idx] 의 원소와 같은지 확인한다.
     (이때 idx 는 만들려고 하는 수열에서 몇번째 숫자인지를 나타내는 변수이다.)
  3. 같다면 idx 를 증가시키고 스택에서 꺼내고 - 를 출력한다.

• 위 반복이 종료된 후에도 스택에 숫자가 남아있다면, 입력 받은 수열은 만들 수 없는 수열이므로, NO 를 출력한다. 그렇지 않으면 + 와 - 를 출력한다.

• + 와 - 를 출력하는 경우, 출력하지 않을수도 있으므로 StringBuilder 를 사용한다.