백준 25556번: 포스택

문제: https://www.acmicpc.net/problem/25556

문제 풀이

그리디

s1, s2, s3, s4 = 각 스택의 가장 마지막에 들어간 수, 스택이 비었으면 0

모든 스택에 수가 내림차순(나중에 들어간 수가 더 큼)으로 들어가야 함

현재 스택에 넣어야 하는 수 i와 s1, s2, s3, s4를 비교해 i가 더 큰 스택을 찾아 i를 넣음

i를 넣을 수 있는 스택이 없다면 NO 출력 후 프로그램 종료

모든 원소를 스택에 넣을 수 있다면 YES 출력하면 정답

풀이 설명

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

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

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

1. 순열 $A$의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
2. 순열 $A$의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

즉, 스택에서 먼저 꺼내는 수는 순열의 오른쪽에 위치하므로 원소를 네 개의 스택에 넣을 때 내림차순(마지막에 들어간 수보다 큰 수를 넣어야 함)으로 넣을 수 있는지를 판별하면 된다. 그리고 스택에 수를 집어넣을 때 스택에 들어간 마지막 수만 비교하면 되기 때문에 실제 스택을 구현할 필요 없이 스택의 마지막 수를 저장하는 변수 하나씩만 사용하면 된다.

따라서 각 스택에 들어간 마지막 수를 저장하는 변수 s1, s2, s3, s4를 정의하고 원소가 $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개이므로 처음에 스택이 비었을 때는 0으로 초기화한다. 그 이후 맨 앞 원소부터 현재 스택에 넣어야 하는 수를 i라고 하면 s1, s2, s3, s4와 비교해 i가 더 큰 값이 있는지 판별한다.

i가 s1보다 더 크다면 첫 번째 스택에 넣으면 되므로 s1에 i를 대입하면 되고 그게 아니라면 첫 번째 스택에는 넣을 수 없는 것이므로 다음 스택의 마지막 수 s2와 비교해 두 번째 스택에 넣을 수 있는지 확인한다.

이런 식으로 i를 네 개의 스택 중 넣을 수 있는 곳이 있는지 판별해 스택에 넣는다. 만약 네 개의 스택 모두 집어넣을 수 없다면 스택에 내림차순으로 넣을 수 없다는 뜻이고 이는 네 개의 스택을 이용해 순열을 정렬할 수 없다는 뜻이므로 NO를 출력해주고 프로그램을 종료하면 된다.

만약 모든 원소를 내림차순으로 네 개의 스택에 넣을 수 있다면 순열을 정렬할 수 있는 것이므로 YES를 출력해주면 정답이 된다.

소스 코드

import java.util.StringTokenizer

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    val st = StringTokenizer(br.readLine())
    var s1 = 0
    var s2 = 0
    var s3 = 0
    var s4 = 0
    repeat(N){
        val i = st.nextToken().toInt()
        if(i > s1){
            s1 = i
        } else if(i > s2){
            s2 = i
        } else if(i > s3){
            s3 = i
        } else if(i > s4){
            s4 = i
        } else {
            println("NO")
            return
        }
    }
    println("YES")
}