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

1. 문제

백준 1874번 스택 수열 - https://www.acmicpc.net/problem/1874

✅ 알고리즘 분류 - 자료 구조, 스택

🥈 난이도 - Silver 3

2. 풀이

문제에서도 말했듯이 스택은 제일 나중에 들어간 자료가 제일 먼저 나오는 LIFO(Last In First Out) 특성을 가지는 자료 구조입니다.

스택의 이러한 특성을 이용하면 이 문제를 쉽게 풀 수 있습니다.

n이 6이고 출력된 수열이 4,3,6,5,2,1인 예제로 설명드려보겠습니다.

문제의 조건에 따르면 idx=0 위치에 있는 4가 스택에서 pop되어 출력되려면 스택에 1,2,3,4가 순서대로 push된 후 pop되어야 합니다. (result = “++++-”)

첫번 째 수를 출력했으니 이제 다음 수인 3을 출력시켜봅시다.

다음 수인 3은 이미 스택에 있고 스택의 최상단에 있으므로 pop해주면 3도 출력시킬 수 있습니다. (result = “++++--”)

다음 수인 6은 스택에 없으므로 스택에 넣었던 최대값 4보다 큰 5부터 6까지 push하고 pop합니다. (result = “++++--++-”)

이 이후 5,2,1은 스택을 세번 pop하면 순서대로 출력시킬 수 있게됩니다.
(result = “++++--++----”)

이제 출력을 시키지 못하는 경우를 살펴보겠습니다.

idx = 2까지는 앞과 동일하게 진행됩니다.

이제 idx=3 위치에 있는 숫자 2를 출력 시켜야 하는데 pop을 시키면 숫자 5가 출력되게 됩니다.

이처럼 스택에서 pop한 값이 현재 idx위치에 있는 값과 다른 경우가 출력이 불가능한 경우입니다.

이제 이 과정을 간략히 정리해 보면 다음과 같습니다.

1. 문제의 입력을 일차원 배열에 저장한다.
2. 스택에 넣었던 최댓값+1 (최초에는 1) 부터 배열의 현재 인덱스의 값까지 스택에 push를 하고 그 때마다 결과에 “+”를 추가합니다.
3. 스택에 pop을 하고 pop한 값이 현재 인덱스의 값이랑 동일한지 확인합니다.
4. 동일한 경우에는 인덱스를 1증가시키고 결과에 “-”를 추가합니다. 그리고 이 과정을 인덱스가 n이 될 때까지 반복합니다.
5. 만약 다른경우에는 진행하지 않고 “NO”를 출력하고 종료합니다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int n;
    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        for (int i=0; i<n; i++)
            arr[i] = Integer.parseInt(br.readLine());
        getResult();
    }

    public static void getResult() {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int inc = 1;
        int idx = 0;
        while (idx < n) {
            while (inc <= arr[idx]) {
                stack.add(inc++);
                sb.append("+").append("\n");
            }
            if (stack.pop() != arr[idx]) {
                System.out.println("NO");
                return;
            }
            sb.append("-").append("\n");
            idx++;
        }
        System.out.println(sb);
    }
}

4. 결과