[PS] 백준 25556 포스택

문제

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

길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다.
스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다. 포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

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

순열
$A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
순열
$A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자

---

분석

처음에 문제가 잘 이해가 되지 않았다. 따라서 다음과 같이 정리해 보았다.

• 1. 정렬을 위한 알고리즘이다.
• 2. 하지만 정렬에 실패할 수 있다.
• 3. 결과적으로 오름차순 정렬을 유도해야 한다.
  • 3-1. 따라서 스택 내부는 오름차순을 유지해야 한다.
  • 3-2. 따라서 순열의 값 i와 임의의 스택 s에 대해, s.top보다 i가 크면 s에 i를 넣을 수 있다.

주어진 테스트 케이스를 스택에 넣어보자.

테스트 케이스1.

순열이 4 3 6 7 8 9 10 2 1 5일 때,

스택1	스택2	스택3	스택4
4		3		2		1
6		5
7
8
9
10

순열의 처음부터 끝까지, 위의 규칙에 따라 스택에 넣을 수 있다. 뺄 때는 각 스택의 top을 비교해 가장 큰 수를 꺼내면 될 것이다.

테스트 케이스2.

순열이 5 4 3 2 1일 때,

스택1	스택2	스택3	스택4
5		4		3		2

마지막 1을 넣으려고 할 때 규칙에 맞는 스택을 고를 수 없다. 따라서 해당 순열에 대한 정렬을 진행할 수 없다.

---

풀이

JAVA

실제로 스택을 사용할 필요는 없어 보인다.
'판별'에 사용하는 값은 각 스택의 top이므로, 각 스택의 top을 의미하는 tops 배열만을 이용한다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] tops = new int[4];

        String result = "YES";
        first: for (int i : arr) {
            for (int j = 0; j < tops.length; j++) {
                if(i > tops[j]) {
                    tops[j] = i;
                    continue first;
                }
            }
            result = "NO";
            break;
        }
        System.out.println(result);
    }
}

입력 받는 부분은 건너뛰고,

판별하는 부분.
임의의 순열 값 i에 대해,
IF tops 배열의 값보다 큰 경우 해당 스택에 push하는 걸 의미한다. tops[j]에 i를 넣음으로써 표현한다. 이 경우, 'YES' 플로우를 계속 진행한다.
ELSE i를 넣을 스택이 없음을 의미한다. 'NO' 플로우이며 즉시 루프를 이탈한다.

Kotlin

fun main() {
    val br = System.`in`.bufferedReader()
    br.readLine()
    val list = br.readLine().split(" ").map(String::toInt)
    val tops = IntArray(4)

    var result = "YES"
    first@for (i in list) {
        for (j in tops.indices) {
            if(i > tops[j]) {
                tops[j] = i;
                continue@first
            }
        }
        result = "NO"
        break;
    }
    println(result)
}

StringTokenizer를 써서 비용을 낮출 수 있다.

결과

---