[백준 골드5] 25556번 포스택 / Java

문제

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

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

포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다.

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

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

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.

입력

첫째 줄에 순열의 길이 N이 주어진다. (1≤N≤100000)

둘째 줄에 순열 A의 원소 A_i가 공백으로 구분되어 주어진다. 모든 A_i는 1 이상 N 이하의 서로 다른 정수임이 보장된다.

출력

포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.

 

아이디어

우선, 문제를 보자마자 든 생각은 후입선출 구조를 가진 Stack을 써야할 것같다는 생각이였다.

Stack<Integer>의 배열을 만들고 한 번에 처리하면 될 것같다.

 

임의로 들어온 숫자들을 4개의 스택에 넣고 앞에서부터 제거하면서 하나의 리스트에 넣었을때, 1~N까지 오름차순으로 정렬되어야 하니까,

스택이 비어있는지를 확인하고, 비어 있다면 삽입. 비어 있지 않다면 peek()를 사용해서 나온 숫자와 현재 넣으려고 하는 숫자의 대소를 비교한 후, 넣으려고 하는 숫자가 더 크다면, 다음 스택으로 넘어가고 4개의 스택 모두에 넣지못한다면 NO를 출력한다.

 

이렇게 넣게되면 스택에는 임의의 숫자들이 오름차순으로 정렬될 것이고 앞에서부터 뺀다면 정렬이 되어 있을 것같다.

소스코드

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

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());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        //비교를 위한 가장 작은 수를 각 스택에 삽입한다.
        Stack<Integer>[] stacks = new Stack[4];
        for(int i=0; i<4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        //스택의 peek보다 큰 수라면 삽입하기
        for(int i=0; i<n; i++) {
            boolean flag = false;
            for(int j=0; j<4; j++) {
                if(stacks[j].peek() < arr[i]) {
                    stacks[j].push(arr[i]);
                    flag = true;
                    break;
                }
            }

            //모든 스택에 삽입하지 못 했다면
            if(!flag) {
                System.out.println("NO");
                return;
            }
        }

        //순열 청소가 완료되면
        System.out.println("YES");

    }
}

 

결과

맞았다!

후기

스택이라는 자료구조을 알고, Stack 자료형과 메서드들에 대해서 안다면 어렵지는 않은 문제같다.

문제를 보고 어떤 알고리즘을 사용해야하는지 파악할 수 있는 문제같다.

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

25556번: 포스택