[Baekjoon/Java] 포스택

문제

25556번: 포스택

풀이

N=10, A={4,3,6,7,8,9,10,2,1,5} 일 때 4개의 Stack에 아래와 같이 삽입한다.

결과가 {1,2,3,4,5,6,7,8,9,10} 이어야하고 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치해야하므로 각 4개의 Stack에 담긴 Element를 가장 큰 수부터 차례대로 아래와 같이 꺼낼 수 있다.

차례대로 Stack에서 가장 큰 수를 차례대로 꺼낼 수 있게하는 조건은 Stack에 값을 Push할 때 반드시 작은 값이 아래로 가고 큰 값은 반드시 위에 쌓여야한다. e.g. {1, 3, 4} (O), {3, 1, 4} (X)

따라서 값을 Stack에 넣을 수 있는지 판단하는 아래의 조건 중 한 가지를 만족시켜야한다.

1. 비어있는 스택
2. 스택의 마지막 element < 현재 입력 값

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

public class Postech {  
    public static void main(String[] args) {
        //입력
        Scanner scanner = new Scanner(System.in);  
        int N = scanner.nextInt();  
        String[] A = new String[N];  
        for (int i=0; i<N; i++) {  
            A[i] = scanner.next();  
        }  

        HashMap<Integer, Stack<Integer>> idxToStack = getIdxToStack();  

        for (String n : A) {  
            int num = Integer.parseInt(n); //값 비교를 위해 int로 변환
            boolean isPush = false; //현재 입력 값이 stack에 삽입되었는지에 대한 여부  
            for (int i=0; i<4; i++) {  
                Stack<Integer> curStack = idxToStack.get(i);  
                //stack이 비어있거나, "stack의 마지막 element"가 현재 입력값보다 작다면 push 가능한 stack으로 판단  
                if (curStack.size()  0 || curStack.peek() < num) {  
                    curStack.push(num);  
                    isPush = true;  
                    break;  
                }  
            }  
            //현재 입력 값이 어떤 stack에도 push되지 않았다면 순열을 청소할 수 없는 것으로 판단  
            if (!isPush) {  
                System.out.println("NO");  
                return;  
            }  
        }

        System.out.println("YES");  
    }  

    /**  
    * 4개의 비어있는 Stack 생성  
    * index를 key로 지정하고 Stack<Integer>를 value로 가지는 Map을 반환  
    * @return {0: Stack<Integer>, 1: Stack<Integer>, 2: Stack<Integer>, 3: Stack<Integer>}
    */
    private static HashMap<Integer, Stack<Integer>> getIdxToStack() {  
        HashMap<Integer, Stack<Integer>> idxToStack = new HashMap<>();  
        idxToStack.put(0, new java.util.Stack<>());  
        idxToStack.put(1, new java.util.Stack<>());  
        idxToStack.put(2, new java.util.Stack<>());  
        idxToStack.put(3, new java.util.Stack<>());  
        return idxToStack;  
    }  
}

 

Stack을 활용하는 문제
시간복잡도: O(n)