25556번 (포스택)

han.user();·2023년 3월 13일
0

백준 온라인 저지

목록 보기
1/7
post-thumbnail

스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO:Last In First Out)이다. 즉, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

스택에 데이터를 넣는 작업을 푸시(push)라고하고 꺼내는 것을 팝(pop)이라고 한다.
또, 푸시와 팝이 이루어지는 쪽을 탑(top)이라하고, 그 반대쪽인 스택의 가장 아랫부분을 바텀(bottom)이라고 한다.

피크(peek) 메소드는, 스택의 최상위 요소를 반환하지만, 제거하지는 않는다.
따라서 스택의 최상위 요소를 확인할 때 유용하게 사용된다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.peek(); // top = 3

출처 : java2blog.com


백준 25556번 (포스택) - 문제 바로가기

문제

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

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

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

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

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

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


입력

첫째 줄에 순열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000) 
둘째 줄에 순열 A의 원소들은 공백으로 구분되어 주어진다.
모든 원소들은 1 이상 N 이하의 서로 다른 정수임이 보장된다.


출력

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


예제 입력 1

10
4 3 6 7 8 9 10 2 1 5
예제 출력 1
YES

예제 입력 2

5
5 4 3 2 1
예제 출력 2
NO


내가 제출한 코드

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

public class Mian {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 정수 N 입력받기

        // N을 통해 배열 만들기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        //스택 만들기 4개
        Stack<Integer>[] stacks = new Stack[4];
        for (int i = 0; i < 4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0); // 모든스택에 0
        }
        for (int i = 0; i <n; i++) {
            boolean push = false;
            for (int j = 0; j <4; j++) {
                if(stacks[j].peek()<arr[i]){
                    stacks[j].push(arr[i]);
                    push = true;
                    break;
                }
            }
            if(!push){
                System.out.println("NO");
                return; // 나가기
            }
        }
        System.out.println("YES");
    }
}
profile
I'm still hungry.

0개의 댓글