[Java/백준 GOLD 5] 25556번: 포스택

문제링크 [https://www.acmicpc.net/problem/25556]

 

풀이 Git링크[ github ]

 

문제 설명

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

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

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

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

포닉스가 주어진 순열을 청소할 수 있는지 판별해 보자.첫째 줄에 순열의 길이 N이 주어진다. (1≤N≤100000)

출력

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

 

 

풀이

이문제를 풀때 이름 그대로 스택을 이용하였습니다.

일반 비어있을때 , Stack top보다 클경우 에는 push를 해줍니다.

그이외의 경우에는 다음스택으로 넘깁니다.

 

만약 4개의 스택이 다 불가능 할경우 NO를 출력후 메서드를 멈춥니다.

 

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

public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> stack3 = new Stack<>();
        Stack<Integer> stack4 = new Stack<>();
        String[] split = sc.nextLine().split(" ");
        for (int i = 0; i < n; i++){
            if(stack1.empty() || stack1.peek() < Integer.parseInt(split[i])){
                stack1.push(Integer.parseInt(split[i]));
            }else if(stack2.empty() || stack2.peek() < Integer.parseInt(split[i])){
                stack2.push(Integer.parseInt(split[i]));
            }else if(stack3.empty() || stack3.peek() < Integer.parseInt(split[i])){
                stack3.push(Integer.parseInt(split[i]));
            }else if(stack4.empty() || stack4.peek() < Integer.parseInt(split[i])){
                stack4.push(Integer.parseInt(split[i]));
            }else {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");


    }
}

 

사용한 메서드

boolean stack.empty() :  스택이 비어있을 경우 True  비어 있지 않을경우 False

Object   stack.peek()   : 스택의 top을 반환한다 단 삭제는 하지않는다.