백준25556번) 포스택

https://www.acmicpc.net/problem/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의 원소Ai가 공백으로 구분되어 주어진다. 모든 Ai는 1 이상 N 이하의 서로 다른 정수임이 보장된다.

 

◇ 출력

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

 

---

◆ 풀이

Stack은 후입선출 형태의 자료구조다.

그렇기 때문에 만약 Stack이 1개라면, 가장 먼저 가장 작은 값이, 가장 마지막에 가장 큰 값이 들어가야 할 것이다. 오름차순으로 정렬되어있는 수열이 아닌 경우 무조건 NO가 출력된다.

 

Stack이 2개라면 어떨까?

순열 A의 길이가 5로 가정해보겠다.

5, 2, 3, 4, 1

s1에 먼저 5를 집어 넣는다.

그리고 이상적이라면 다음으로는 이어 지는 수인 4를 s1에 넣어거나 최소값을 다른 스택에 넣어야 한다.

하지만 2가 왔다. 우선 s2에 넣어본다.

s1 = {5 } / s2 = {2}

2 이후에는 3과 4가 오는 것이 이상적이기 때문에 다시 3과 2를 s2에 넣는다.

s1 = {5} / s2 = {2, 3, 4}

그런데 마지막으로 남은 수 1은 그 어느 스택에 넣어도 문제가 된다.

어느 쪽에 넣더라도 가장 마지막에 뽑힐 수 있는 가능성이 없다.

 

위 전개를 보았을 때, 순열 A가 청소될지 여부는 아래 조건에 의해 결정될 것이다.

1. 현존하는 Stack 중 적절한 곳에 배치한다.
2. 단, 그 Stack에 이미 배치되어있는 숫자 중 넣으려는 숫자보다 큰 수는 있어서는 안 된다.
3. 만약 배치할 수 있는 Stack이 존재하지 않는 경우에는 청소할 수 없을 것이다.

이 코드는 다음과 같이 작성할 수 있다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 입력 받음
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] splitedString = scanner.nextLine().split(" ");

        // Stack 준비
        Stack[] stacks = new Stack[4];
        for (int i = 0, iMax = stacks.length; i < iMax ; i++) {
            stacks[i] = new Stack();
        }

        // 순열 데이터 각 Stack에 add
        boolean result = true;
        for (int i = 0, iMax = splitedString.length; i < iMax ; i++) {
            Integer value = Integer.parseInt(splitedString[i]);
            boolean added = false;

            for(int j=0, jMax = stacks.length; j<jMax; j++){
                Stack stack = stacks[j];
                if(stack.stream().anyMatch(x-> (Integer)x>value))
                    continue;

                added = stacks[j].add(value);
                break;
            }

            if(!added){
                result = false;
                break;
            }
        }

        System.out.println(result ? "YES" : "NO");
    }
}

하지만 이 코드를 제출했더니 결과는...

보기 좋게 실패했다.

지금 보니 시간 제한이 1초였다.

그렇다면 시간 복잡도를 낮추기 위해 어떤 처리가 필요할까?

고민을 하다가 peek()이라는 함수의 존재를 기억해냈다.

매번 넣을 때마다 모든 데이터를 확인할 필요 없이, 가장 마지막에 넣은 값만 비교한다면 시간 복잡도를 줄일 수 있을 것이다.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 입력 받음
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] splitedString = scanner.nextLine().split(" ");

        // Stack 준비
        Stack[] stacks = new Stack[4];
        for (int i = 0, iMax = stacks.length; i < iMax ; i++) {
            stacks[i] = new Stack();
        }

        // 순열 데이터 각 Stack에 add
        boolean result = true;
        for (int i = 0, iMax = splitedString.length; i < iMax ; i++) {
            Integer value = Integer.parseInt(splitedString[i]);
            boolean added = false;

            for(int j=0, jMax = stacks.length; j<jMax; j++){
                Stack stack = stacks[j];
                // stream()을 호출하여 모든 데이터를 확인하는 대신!
                // peek() 함수를 사용한다!
                if(!stack.isEmpty() && (Integer)stack.peek()>value)
                    continue;

                added = stacks[j].add(value);
                break;
            }

            if(!added){
                result = false;
                break;
            }
        }

        System.out.println(result ? "YES" : "NO");
    }
}

 

해냈다!