[BOJ] 25556 - 포스택 (JAVA)

문제출처 : 링크텍스트

---

문제 요약 설명

• 포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있습니다.

• 길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다.

• 순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 $1, 2, 3, \cdots N$으로 만들어야 한다.

• 순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.

• 순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.

• 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
  포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

---

풀이방법

어디가서 이야기하면 공부잘하는 것처럼 보일것만 같은 제목의 문제입니다. 그러나 문제 제목과는 다르게 스택 자료구조와는 99.99% 상관이 없고 대신 수학적인, 그리디한 사고를 요구합니다.

이 문제의 핵심은 사용할 스택 4개를 초기화시켜 준비할 때, 4개의 스택에 초기값 0을 넣어서 초기화하는데, 이는 순열을 "청소" 하기 위해서는 스택의 마지막에는 항상 그 이전의 스택 원소들보다 큰 수가 추가되어야 하기 때문에, 수를 서로 비교하는 절차를 편하게 하기 위함입니다. 순열의 원소는 1부터 N까지의 정수로 이루어져 있으므로, 0을 스택의 첫 원소로 한다면 항상 순열의 원소들보다 작아 처리가 간편하도록 도와줄 수 있습니다.

또한, 순열을 순회하다가 현재 스택에 추가하여야할 숫자보다 작은 수를 4개의 스택 마지막 원소들 중에서 찾지 못하였다면, 이미 청소를 실패한 것이므로 연산을 중단하여야 시간 초과를 막을 수 있습니다.

• 입력을 받고, 4개의 스택을 준비한다.
• 순열을 순회하며, 현재 숫자보다 작은 마지막 원소를 가진 스택에 숫자를 추가한다.
  - 이 때, 현재 숫자와 스택 마지막 원소와의 차가 가장 작은 스택을 찾아 현재 숫자를 추가한다.
• 만약 모든 스택에서 현재 숫자보다 작은 스택의 마지막 원소를 찾지 못한다면, 순열을 청소하는데 실패한 것이므로 즉시 중단하고 실패를 출력한다.

---

문제풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class BOJ25556_포스택 implements Application {
    static Scanner sc = new Scanner(System.in);
    static int[] array;
    static boolean flag = true;
    static ArrayList<Stack<Integer>> stacks;

    public static void main(String[] args) {
        int N = sc.nextInt();
        sc.nextLine();
        array = Arrays.stream(sc.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        // 네개의 스택 준비
        stacks = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            stacks.add(new Stack<>());
            stacks.get(i).add(0); // 비교를 위해 초기화
        }
        //풀이
        for (int i = 0; i < array.length; i++) {
            findAndPushRightPosition(i);
            if (!flag) {
                break;
            }
        }
        if (flag) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    private static void findAndPushRightPosition(int i) {
        int minDiff = Integer.MAX_VALUE;
        int minStk = -1;
        // 포스택의 원소와의 차가 가장 작은 원소를 가진 포스택 찾기
        for (int j = 0; j < stacks.size(); j++) {
            Stack<Integer> stk = stacks.get(j);
            if (stk.peek() < array[i]) { //  현재 숫자보다 작을 경우
                int diff = array[i] - stk.peek();
                if (diff < minDiff) {
                    minDiff = diff; // 업데이트
                    minStk = j; // 몇 번 스택인지 기록
                }
            }
        }
        if (minStk != -1) { // 집어넣을 만한 스택이 있엇다면
            stacks.get(minStk).push(array[i]); // 차이가 가장 작은 쪽에 푸시
        } else { // 현재 숫자보다 큰 녀석밖에 없다면 실패
            flag = false;
        }
    }
}

---