Stack의 활용 문제 - BOJ 25556번 포스택

문제

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

25556번: 포스택

 

 

 

문제 접근

• 순열의 "청소"의 정의는 문제에 정의되어있는 일련의 순서를 진행하였을 때 순열의 전체적인 모습이 오름차순으로 정렬될 수 있는가를 묻는다.
• 스택은 LIFO로 나중에 들어오는 수가 먼저 나가기 때문에 문제의 과정 중 3번을 살펴보면 스택의 내부가 오름차순으로 되어 있어야 한다.
• 다음의 TC를 보자

10
4 3 6 7 8 9 10 2 1 5

• 만약 어떤 스택에 4가 먼저 들어온 뒤, 그 스택에 3을 넣는다고 생각해보자. 후입선출의 원리에 의해 스택에서 3이 먼저 나가게 되고 4가 그 이후에 나가게 된다.
• 하지만 이를 뒤집어 버리면 4, 3으로 나열되기 때문에 오름차순이 되지 못하고 이는 적합한 방법이 아니다.
• 그렇다면 4 이후 3을 다른 스택에 넣고, 6을 4의 다음으로 넣는다고 가정하자. 그렇게 되면 6을 먼저 빼고, 4를 pop한뒤, 3을 pop 함으로서 6, 4, 3이 되고 이를 반대로 나열하면 3, 4, 6으로 오름차순이 되는 것을 확인할 수 있다.
• 따라서 우리는 다음의 결론을 얻을 수 있다.
  • 어떤 순열 A를 문제의 순서에 따라 청소할 수 있다는 것은 4개의 스택에 수들이 오름차순으로 들어가 있다는 것과 동치이다.
• 즉 입력으로 들어오는 순열 A에 대해 스택에 오름차순으로 모두 쌓을 수 있는지를 묻는 문제이다.

 

 

풀이 구현

• 위의 조건을 알고 있는 상태에서 가장 심플하게 구현하는 방법은  Stack의 배열 4개를 만들어 그 top을 비교하게 하는 방법이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class StudyCode {
    static Deque<Integer>[] stack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] per = new int[N];
        for (int i = 0; i < N; i++){
            per[i] = Integer.parseInt(st.nextToken());
        }

        stack = new Deque[4];
        for (int i = 0; i < 4; i++){
            stack[i] = new ArrayDeque<>();
            stack[i].addLast(0);
        }

        boolean result = chk(per);
        String ans = result ? "YES" : "NO";

        System.out.println(ans);
    }

    public static boolean chk(int[] per){
        for (int element: per){
            boolean flag = false;

            for (int i = 0; i< 4; i++){
                if (element > stack[i].peekLast()){
                    stack[i].addLast(element);
                    flag = true;
                    break;
                }
            }

            if (!flag){
                return false;
            }
        }

        return true;
    }
}

• 청소의 가능 유무를 판단하는 함수 chk를 보도록 하자. 위에서 설명한 그대로를 구현한 것임을 알 수 있다.
• 이때 스택이 비어있다면 0으로 간주하므로, 모든 스택을 초기화함과 동시에 0을 push하여 조건을 만족하도록 하였다.

 

 

정리

• 다른 방법으로는 해당 문제가 stack의 top 부분만들 검사한다는 것에 착안하여 top만 관리하는 배열을 하나 만들어 갱신을 지속하도록 하는 방법이 있다.(링크: https://velog.io/@studyhard/%EB%B0%B1%EC%A4%80-25556-%ED%8F%AC%EC%8A%A4%ED%83%9D)
• 구현 형태는 위와 비슷하나, stack[i].peek 대신에 top[i]로 간단히 비교할 수 있다는 점이 매력적이다. 개인적 생각으로는 시간복잡도 차이는 거의 나지 않는것 같고, 공간복잡도에서 조금 차이가 생길 수 있을 것 같다.
• 위 문제의 시간복잡도는 입력받은 순열의 길이 N을 스택 4개에 나누어 담는 것이기 때문에 O(4 * N)이 되며 이는 O(N)으로 수렴된다.