[백준] 25556번: 포스택 - Java

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

---

• 문제

 

• 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 정수를 저장할 수 있는 스택 배열 생성 크기 4
        Stack<Integer>[] stacks = new Stack[4];
        for (int i = 0; i < 4; i++) {
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        boolean isPossible = true;    // 규칙에 따라 스택에 들어갈 수 있는지 여부 확인

        for (int i = 0; i < n; i++) {
            int number = Integer.parseInt(st.nextToken());
            boolean isPushed = false;
            for (int j = 0; j < stacks.length; j++) {
                if (number > stacks[j].peek()) {
                    stacks[j].push(number);
                    isPushed = true;
                    break;
                }
            }
            
            if (!isPushed) {
                isPossible = false;
                break;
            }
        }

        System.out.println(isPossible ? "YES" : "NO");
        br.close();
    }
}

 

스택을 활용한 알고리즘 문제이다. 

주어진 순열을 스택을 사용하여 오름차순으로 정렬할 수 있는지 판별해야 한다.

 

1. 길이가 N인 수열 A와 네 개의 비어 있는 스택을 가지고 시작합니다.

2. 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입합니다.

3. 모든 원소를 스택에 삽입한 후, 네 개의 스택에서 수를 꺼내어 오른쪽에서 왼쪽으로 나열한다.
    이때, 가장 처음에 꺼낸 수가 맨 뒤에, 가장 나중에 꺼낸 수가 맨 앞에 위치해야 함.

4. 스택 특성상, 먼저 넣은 값은 제일 나중에 꺼낼 수 있기 때문에, 스택에 숫자를 넣을 때 스택의
    최상단 값보다 큰 경우에만 삽입해야 한다.

 

위에 코드는 4개의 스택을 생성하고 각각 0으로 초기화 한 뒤, 현재 숫자랑 스택의 맨 위에 숫자랑 비교하여

현재 숫자가 더 크다면 스택에 쌓는 걸 반복하고 있다.

스택에 숫자가 다 들어갔다면 isPossible = true;  가 되어 YES를 출력하고, 그렇지 않다면 NO를 출력한다.

 

처음에 Stack의 특성, 오른쪽에서 왼쪽으로 나열을 이해하지 못해서 한참을 고민했다...

예제입력 1을 조건에 맞게 넣으면

스택 1: 4, 6, 7, 8, 9, 10

스택 2: 3, 5

스택 3: 2

스택 1: 1

이렇게 들어가는데, 분명 오름차순 정렬이고 스택은 마지막에 들어간 것부터 꺼내오는데 어떻게

1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 된다는 거지 1, 2, 3, 5, 4, 6, 7, 8, 9, 10이 맞는 거 아닌가 하고 머리를 쥐어짰다...

스택 1에서 10, 9, 8, 7, 6까지 꺼내고 스택 2에서 5 다시 스택 1에서  4를 꺼낼 수 있다는 것을 생각하지 못함