[JS] 백준 1874번 스택 수열

---

문제 링크

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

풀이 전략

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

코드 

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
rl.on("line", function (line) {
    input.push(+line);
}).on("close", function () {
    console.log(solution(input));
    process.exit();
});

const solution = (arr) => {
    const n = arr.shift();
    const stack = [];
    let answer = "";
    let val = 1;

    for (let i = 0; i < n; i++) {
        const elem = arr[i];

        while (val <= elem) {
            stack.push(val++);
            answer += "+\n";
        }
        if (stack.pop() !== elem) return "NO";
        answer += "-\n";
    }

    return answer;
};

 

회고

만약 스택이 arr에 있는 어떤 수까지 채워졌다면 무조건 그 수를 빼야하는 규칙을 알아낼 수 있다면 쉽게 풀 수 있다. 그리고 그렇게 채운후 맨위에있는 스택이 현재 arr의 수와 다르다면 스택을 이용해 수열을 만들 수 없다는 뜻이므로 no를 리턴한다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)