BASIC | 기차 운행

📌 문제

그림처럼 열차가 들어갔다 나올 수 있는 플랫폼이 있다. 열차가 1번부터 3번까지 순서대로 들어온다고 했을 때, 입력 순서대로 나갈 수 있는지 없는지 판단하는 프로그램을 작성하시오. 입력은 차량 순서 번호가 적혀 있는 배열이며, 가능 여부에 따라 true 혹은 false를 반환한다.

입출력 예

prices	return
[1, 2, 3]	true
[3, 2, 1]	true
[3, 1, 2]	false

✨ 해결 방법

열차는 무조건 1, 2, 3 순서로 들어옵니다.
내보내고 싶은 순서가 정해졌을 때, 어떤 수를 stack에 저장하고, 어떤 수는 저장하자마자 내보낼지 정해야 합니다.

만약 1, 2, 3 순서로 나갈 경우 1 이 들어오자마자 내보내고, 2가 들어오자마자, 3이 들어오자마자 모두 pop 하여 내보내면 됩니다.

3, 2, 1 순서로 내보낼 경우 1, 2, 3을 들어오는대로 모두 stack에 보관해뒀다가 3부터 역순으로 내보냅니다.

2, 1, 3의 경우 1, 2까지 저장하고 2를 바로 내보내고, 1, 3이 남은 상태에서 순서대로 내보냅니다.

마지막으로 3, 1, 2 의 경우 1, 2, 3을 순서대로 저장하는데, 3을 내보내고 2에 가로막혀 1을 내보낼 수 없으므로 불가능한 경우입니다.

💻 solution 1

function answer(train) {
    const stack = [];
    let num = 1;
  
    for (let i = 0; i < train.length; i++){
        while (stack.length === 0 || stack[stack.length - 1] < train[i]){
            stack.push(num++);
        }

        if (stack[stack.length - 1] == train[i]){
            stack.pop();
        } else {
            return false;
        }
    }
    return true;

}

이어서 train이 [ 2, 1, 3 ] 일 때를 가정하여 설명하겠습니다.

0 번째 요소 2에 대하여, [ 1, 2, 3 ]의 순서대로 num 을 증가시키면서 stack에 넣습니다. 우선, stack이 비어있을 경우 1을 넣습니다. 그 후 방금 넣은 값인 stack의 마지막 값 1과, 2의 값을 비교합니다. 2를 가장 먼저 내보내야 하기 때문에 마지막 요소는 2가 되어야 합니다. 따라서 다시 한 번 push 합니다.
현재 stack은 [ 1, 2 ] 입니다.

또 한번 넣게 된다면 2와 2를 비교하게 됩니다. 두 수는 같기 때문에 반복문에서 빠져 나와 아래의 조건문을 실행합니다. 마지막 요소인 2가 나오게 되고 stack은 [ 1 ] 이 됩니다.

그렇다면 다시 반복문을 수행할 수 있는데, i값이 증가하여 1번째 인덱스인 1과 비교합니다. 마지막 stack 값인 1과 같으므로 반복문을 나와 pop 합니다. 현재 stack은 [ ] 빈 배열입니다.

마지막으로 i 값을 증가시면 i = 3, stack은 빈 배열이므로 stack = 3이 되고, 마지막 요소와 3이 같아지므로 반복문을 나와 pop을 하면 stack이 모두 비워지고 결과는 true가 됩니다.

이때, 반복문을 나와 조건문을 실행함에도 조건 또한 맞지 않을 때 (예를 들어 [3, 1, 2]) 결과값은 false가 됩니다.

💻 solution 2

function answer(train) {
    const stack = [];
    let num = 1;

    if (!Array.prototype.peek) { //peek라는 내장 함수가 없다면 만든다
        Array.prototype.peek = function () {
            return this[this.length - 1];
        };
    }

    if (!Array.prototype.isEmpty) {
        Array.prototype.isEmpty = function () {
            return this.length == 0;
        };
    }

    for (let i = 0; i < train.length; i++){
        while (stack.isEmpty() || stack.peek() < train[i]){
            stack.push(num++);
        }

        if (stack.peek() == train[i]){
            stack.pop();
        } else {
            return false;
        }
    }
    return true;

}

같은 기능을 하지만 위 처럼 모듈화하여 작성할 수도 있습니다.