백준 1874 스택 수열 | JavaScript 배열 비교

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

수열을 만드는 방식을 먼저 확인해야한다.
입출력 예시 1번을 예를 들어보면 아래와 같은 방식으로 수열이 만들어지게 된다.

(파란색이 만들어지는 수열)

이 예시를 이용하여 push, pop을 하는 조건을 찾으면 아래와 같다.

• 1~n까지 모든 수는 push되어야 한다.
• 스택의 마지막 값을 수열의 첫번째 값부터 계속 비교한다.
  • 값이 같으면 pop하고, 비교할 수열의 인덱스를 증가시킨다.
• n까지 모두 push한 후에는 스택에 남아있는 모든 값을 pop한다.
• 이 과정에서 push, pop할 때마다 이에 대한 정보를 저장한다.
• 주어진 수열을 만들 수 있다면 저장한 push,pop 정보를 출력하고, 만들 수 없다면 "NO"를 출력한다.

stack (스택)
sequence (만들어질 수열)
answer (push,pop 정보를 저장할 배열)

function customPop(value) {
  stack.pop();                         
  sequence.push(value);
  answer.push("-");
}

pop을 한번 할 때 스택에서 값을 꺼내고, 꺼낸 값을 수열에 추가하고, pop정보("-")를 추가해야한다.
여러 조건에서 쓰일 것 같아서 함수로 분리하여 customPop을 새로 만들었다.

for (let i = 1; i <= n; i++) {
    stack.push(i);
    answer.push("+");

    if (array[index] == i || array[index] == stack[stack.length - 1]) {
      index++;
      customPop(i);
    }
  }

  while (stack.length !== 0) {
    customPop(stack[stack.length - 1]);
  }

기본적인 로직은 이렇게 구현했다.

1부터 n까지 반복하면서 항상 push를 한다. 그리고 새롭게 push하는 값(i)이 수열의 index번째 수와 같거나, stack의 마지막 값이 수열의 index번째 수와 같은 경우 index를 증가시키고, customPop()을 호출한다.
반복이 완료된 후에는 스택이 빌 때까지 pop을 반복한다.

얼핏 보면 잘 해결한 것 같지만 이 풀이에는 문제가 있다😅
pop을 연속해서 해야하는 경우에, 이를 처리하지 못하고 다음 수로 넘어가버린다..

customPop()이 동작한 후에, 또다시 if문으로 돌아와 조건을 체크해야한다.
그렇기 때문에 if문이 아닌, while문으로 고치면 원하는 대로 동작하게 된다.

while (stack.length > 0 && newArray[index] === stack[stack.length - 1]) {
  customPop(stack[stack.length - 1]);
  index++;
}

스택에 넣었다 빼면서 수열을 만들었으니, 이제 만들어진 수열이 주어진 수열과 동일한지 확인하면 된다.
배열의 경우에는 등호로 비교할 수 없다. 객체이기 때문에 등호를 이용하면 값을 비교하는 것이 아니라, 주소를 비교한다. (=항상 false가 나온다)

대신 직접 순회하면서 비교하거나 문자열로 변환하여 비교할 수 있다.
하지만 직접 순회하며 비교하는 경우 시간복잡도가 O(n)으로 매우 커지기 때문에 효율이 좋지 않다. 문제에서 주어진 n의 범위가 (1 ≤ n ≤ 100,000)이기 때문에, 최악의 경우에는 비교를 10만번 해야한다 .. 🫨

  JSON.stringify(array) == JSON.stringify(sequence)
    ? console.log(answer.join("\n"))
    : console.log("NO");

문자열로 변환하여 비교하여 같다면 answer 값에 개행을 추가하여 출력하고, 다르다면 "NO"를 출력한다.

전체 코드

const stack = [],
  sequence = [],
  answer = [];

function customPop(value) {
  sequence.push(value);
  stack.pop();
  answer.push("-");
}

function solution(n, array) {
  let index = 0;

  for (let i = 1; i <= n; i++) {
    stack.push(i);
    answer.push("+");

    while (stack.length > 0 && array[index] === stack[stack.length - 1]) {
      customPop(stack[stack.length - 1]);
      index++;
    }
  }

  while (stack.length !== 0) {
    customPop(stack[stack.length - 1]);
  }

  JSON.stringify(array) == JSON.stringify(sequence)
    ? console.log(answer.join("\n"))
    : console.log("NO");
}

// =====입출력=====

const readline = require("readline");

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

let input = [];

rl.on("line", (line) => {
  if (input.length === 0) {
    input.push(Number(line));
  } else {
    input.push(Number(line));
  }

  if (input.length === input[0] + 1) {
    rl.close();
  }
}).on("close", () => {
  const n = input[0];
  const array = input.slice(1);

  solution(n, array);
});