[JavaScript] 백준 25556 포스택 (JS)

문제 링크

문제 설명

무작위로 나열 되어 있는 N개의 배열에서 4개의 스택으로 하나씩 옮긴 후
숫자가 큰 순서대로 뽑을 수 있는지 확인하는 문제이다.
입력으로 첫줄에는 몇개의 숫자가 주어지는지 N이 주어지고,
두번째 줄에는 N개의 숫자가 무작위로 띄어쓰기를 기준으로 나열 되어있다.
간단한 예시를 들자면
10
4 3 6 7 8 9 10 2 1 5
라는 입력이 주어지면
스택1 - 4 6 7 8 9 10
스택2 - 3 5
스택3 - 2
스택4 - 1
로 저장을 한 후에 큰 순서대로 뽑아 오른쪽으로 넣으면
1-2-3-.....-9-10 이와 같이 숫자를 정렬할 수 있고 이럴 경우 YES를 출력하면 되는 문제이다.

풀이 과정

큰 순서대로 스택에서 값을 가져오고 싶다면 스택에 값을 넣을 때 무조건 큰 값이 위에 오게하면 될 것이다.
위의 생각을 전재로 순서대로 생각해보자.

우선 포스택(FourStack)이라는 클래스(class)를 만들어 주었다.
아래는 해당 포스택 클래스의 로직의 설명이다.

• 요소를 삽입할 때 각각의 스택을 확인
  • 스택이 비어 있을 경우 바로 삽입
  • 스택이 비어 있지 않을 경우
    • 스택 최상단 값 < 삽입할 요소의 경우 스택에 삽입
• 위에 어떤 경우에도 속하지 않을 경우 false 리턴

포스택(FourStack) 클래스 코드

    class FourStack {
        constructor() {
            this.Stack = [[], [], [], []];
        }

        insert(element) {
            let targetIndex = 0;
            for (let i = 0; i < this.Stack.length; i++) {
                if (this.Stack[i].length !== 0) {
                    if (this.Stack[i][this.Stack[i].length - 1] < element) {
                        targetIndex = i;
                        this.Stack[targetIndex].push(element);
                        return true;
                    }
                } else {
                    targetIndex = i;
                    this.Stack[targetIndex].push(element);
                    return true;
                }
            }
            return false;
        }
    }

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
    let N = parseInt(input.shift());
    input = input.shift().split(' ').map(Number);

    class FourStack {
        constructor() {
            this.Stack = [[], [], [], []];
        }

        insert(element) {
            let targetIndex = 0;
            for (let i = 0; i < this.Stack.length; i++) {
                if (this.Stack[i].length !== 0) {
                    if (this.Stack[i][this.Stack[i].length - 1] < element) {
                        targetIndex = i;
                        this.Stack[targetIndex].push(element);
                        return true;
                    }
                } else {
                    targetIndex = i;
                    this.Stack[targetIndex].push(element);
                    return true;
                }

            }
            return false;
        }

    }

    const solution = () => {
        const FS = new FourStack();

        for (let i = 0; i < input.length; i++) {
            let result = FS.insert(input[i]);
            if (!result) {
                return 'NO';
            }
        }
        return 'YES';
    };
    console.log(solution());

후기

저번에 우선순위큐를 직접 구현 해서 그런지 자료구조 문제를 풀면 class를 이용해 구현할 생각이 가장 먼저 든다.
해당 사고 방식이 좋은 방식인지는 아직 정확히 모르겠지만 일단 자료구조 문제를 조금 더 풀면서 생각을 해야겠다.
그리고 이번 문제는 로직을 생각하는 것보다 문제에 대한 이해가 어려웠던 문제였다.