백준 포스택 문제

• 출처: https://www.acmicpc.net/problem/25556

처음에 이거 내용 이해가 조금 어려웠는데, 구현은 그에 비해 쉬웠다. 여기서는 이해에 초점을 맞춰서 설명하겠다. (아래는 본인의 언어로 재구성한 문제 내용이다.)

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

• 순열을 오름차순으로 정렬하는 것이 목적

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

Stack의 어떤 성질을 이용하는가?

Stack은 가장 마지막 값을 꺼낼 수 있다는 특징을 가진다. 이는 "가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다."와 일치하는 내용으로 Stack으로 구현이 가능할 것이다. (물론 문제에서 아예 Stack을 제시하고 있다.)

풀이

즉, 위의 상황을 다시 말하면 맨 뒤에 있는 수(즉, 가장 나중에 넣은 수)가 가장 큰 수가 되어야 한다. 예를 들어, $5,4,3,2,1$ 가 있다고 하자.

• "5"은 1번째 스택에 들어간다.
• "4"은 2번째 스택에 들어간다.
• "3"은 3번째 스택에 들어간다.
• "2"은 4번째 스택에 들어간다.
• "1"은 스택은 4개뿐이라 들어갈 곳이 없다. "1"은 어디에 들어가도 가장 큰 수가 될 수 없다.

즉 우리는 들어갈 스택이 없는 수가 발생하는 경우를 잡으면 된다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 1
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] array = new int[num];
        Stack<Integer>[] stackList = new Stack[4];
        int cnt = 0;

        // 입력 2
        for (int i = 0; i < num; i++) {
            array[i] = sc.nextInt();
        }

        // 포스택 생성

        for (int i = 0; i < 4; i++) {
            stackList[i] = new Stack<>();
        }
        
        // 조건 처리

        for (int item: array){
            for (Stack stack: stackList){
                if (stack.isEmpty() || (int) stack.peek() <= item){
                    stack.push(item);
                    cnt ++;
                    break;
                }
            }
        }
        
        // 출력

        if (cnt == num){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }
}

아직 입력이 익숙하지 않아, Scanner를 통해 단순하게 받아왔다.

핵심1. 조건 처리

        // 조건 처리

        for (int item: array){
            for (Stack stack: stackList){
                if (stack.isEmpty() || (int) stack.peek() <= item){
                    stack.push(item);
                    cnt ++;
                    break;
                }
            }
        }

for문 2번을 활용하여 순열 A에서 숫자를 하나씩 꺼내고, 이를 Stack에 하나씩 넣어보는 시도를 진행한다.

조건1. 스택이 비었거나
조건2. 스택의 가장 위의 값보다 숫자 값이 큰 경우

Stack에 해당 숫자를 넣고 cnt를 증가시켜준다.

핵심2. 출력

        // 출력

        if (cnt == num){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

스택에 넣은 횟수(cnt)와 수열의 길이 (num)를 비교하여 모든 수를 Stack에 넣었다면 "YES"를 출력한다.

느낀 점

아직 입력 함수가 익숙하지 않아, 이를 일부 찾아봤다. 또한, 문제에서 쓰이는 아이디어가 다소 겹치는듯 보이는데 이에 대한 유형화 / 아이디어 정리를 같이 하면 좋을 것 같다.