[백준] 포스택 (JS)

문제

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≤100000)

둘째 줄에 순열 A의 원소 Ai가 공백으로 구분되어 주어진다. 모든 Ai는 1 이상 N 이하의 서로 다른 정수임이 보장된다.

출력

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

풀이

1. 순열 청소가 가능하려면, 주어진 수열이 문제의 조건 1, 2, 3번을 모두 만족하는 순열이어야 한다.

2. 가장 마지막에 꺼낸 숫자가 맨 앞에 있는 숫자이므로, 맨 앞 숫자부터 차례로 조건을 따져 스택에 푸시한다.

3. 스택의 Top과 비교하기 위해 초기값을 0으로 설정한다.

4. 반복문을 진행하면서, 현재 숫자가 A 스택의 Top보다 크면 푸시, 작으면 B 스택의 Top과 비교한다. 이 과정을 D 스택까지 반복한다.

5. 만약 모든 스택의 Top보다 작은 숫자가 나오면 "NO", 모든 숫자를 정상적으로 푸시할 수 있으면 "YES"를 출력한다.

const fs = require("fs");
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");

const [N, sequence] = input;
const sequenceArr = sequence.split(" ").map(Number);
const stack = [[0], [0], [0], [0]]; // 풀이 설명을 위해 A, B, C, D 스택이라고 지칭

for (let i = 0; i < N; i++) {
    let pushFlag = false;
    for (let j = 0; j < stack.length; j++) {
        if (sequenceArr[i] > stack[j][stack[j].length - 1]) {
            stack[j].push(sequenceArr[i]);
            pushFlag = true;
            break;
        }     
    }
    if (!pushFlag) {
        console.log("NO");
        return;
    }
}

console.log("YES");

결론

이 문제는 골드 5 난이도의 스택 문제로, 주어진 순열이 청소가 가능한지 판별하는 문제이다.

핵심은 조건을 거꾸로 생각하면서 순열이 유효한지 판단하는 것이다.
즉, 주어진 순열이 특정 규칙을 따르는 방식으로 정렬될 수 있는지를 스택을 활용해 검증해야 한다.