[JAVA] BOJ 25556 포스택

John·2023년 3월 13일

백준

코테 메모🌼

목록 보기

21/28

스택

개념

stack

LIFO(Last In First Out)
가장 최근에 스택에 추가한 항목이 가장 먼저 제거

자주 사용하는 메소드

메소드	설명
stack.peek()	스택에 마지막으로 저장된 요소를 반환
stack.push(n)	스택에 value 추가
stack.pop()	스택의 peek() 반환, 해당 요소를 제거
stack.size()	스택의 크기 출력
stack.empty()	스택이 비어 있으면 true, 비어 있지 않으면 false를 반환
stack.contains(n)	스택에 n이 존재하면 true, 존재하지 않으면 false 를 반환

참고자료
✨Stack 이란 무엇인가요?

문제 설명

포스택

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

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

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

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

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

입/출력

입력

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

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

출력

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

예제

풀이

package baekjoon;

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

/**
 * @date : 2023-03-13
 * 포스택(25556)
 */
public class BOJ25556 {

    /**
     * 길이가 N인 순열이란, 1 이상 N 이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다.
     *
     * 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다.
     * 순열 A의 모든 원소를 스택에 삽입했다면, 네 개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 네 개의 스택에서 모든 수를 꺼낸다.
     * 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.
     *
     * 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다.
     */
    public static void main(String[] args) {

        String result;

        int sizeOfStacks = 4;
        ArrayList<Stack<Integer>> stacks = new ArrayList<>();

        Scanner sc = new Scanner(System.in);

        // 순열 A의 길이 입력 받기 (ex : 5)
        int N = sc.nextInt();

        // 순열 A의 원소 1 이상 N 이하의 서로 다른 정수 공백으로 입력 받기 (ex : 5 4 3 2 1)
        sc.nextLine();
        String[] elements = sc.nextLine().split(" ");

        // 4개의 Stack 초기화
        for(int i = 0; i < sizeOfStacks; i++) {
            stacks.add(new Stack<>());
            stacks.get(i).push(0);
        }

        // 결과 가져오기
        result = getResult(N, elements, sizeOfStacks, stacks);
        System.out.print(result);
    }

    /**
     *
     * @param N 순열의 길이
     * @param elements 입력받은 순열들의 요소를 가진 배열
     * @param sizeOfStacks 스택의 개수
     * @param stacks 스택
     *
     * @return
     */
    private static String getResult(int N, String[] elements, int sizeOfStacks, ArrayList<Stack<Integer>> stacks) {
        int element;

        for(int i = 0; i < N; i++) {
            element = Integer.parseInt(elements[i]);

            for(int j = 0; j < sizeOfStacks; j++) {
                if(stacks.get(j).peek() < element) {
                    stacks.get(j).push(element);
                    element = 0;
                    break;
                }
            }

            if(element != 0) {
                return "NO";
            }
        }

        return "YES";
    }
}