[백준] 스택 수열 (javascript)

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

1874번: 스택 수열

 

🤔 해결방법

1. 수열의 숫자를 만들기 위해 만들려는 숫자가 스택의 top에 올 때까지 필요한 숫자를 스택에 push

2. 만들려는 숫자가 top에 있으면 pop

3. 만들 수 없는 경우는 'NO'를 반환

 

 

🔑 풀이

처음 문제를 읽었을 땐 한 번에 이해가 잘 가지 않았다.

다음과 같이 예제 1번의 실행 순서를 적어보며 이해했다.

 

1. 첫 번째 숫자인 4를 만들기 위해 1, 2, 3, 4를 차례대로 스택에 push한다.

이 때 result에도 '+'를 4번 push.

2. 스택의 top에 4가 있으므로 4를 pop한다.

이 때 result에도 '-'를 1번 push.

3. 다음 숫자 3을 만들기 위해 현재 스택의 top에 있는 3을 pop 한다.

이 때 result에도 '-'를 1번 push.

4. 다음 숫자 6을 만들기 위해 5, 6을 차례대로 스택에 push한다.

이 때 result에도 '+'를 2번 push.
5. 스택의 top에 6이 있으므로 6을 pop한다.

이 때 result에도 '-'를 1번 push.
6. 다음 숫자 8을 만들기 위해 7, 8을 차례대로 스택에 push 한다.

이 때 result에도 '+'를 2번 push.
...
이런 방식으로 진행된다.

 

따라서 만들려는 숫자가 top이 될 때까지 필요한 수를 스택에 push하고 top에 만들려는 숫자가 오면 pop을 하는 것을 반복하면 된다.

코드는 다음과 같다.

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

  const n = Number(input[0]);
  let stack = [];
  let result = [];
  let currentNumber = 1;

  for (let i = 1; i <= n; i++) {
    const makeNumber = Number(input[i]);

    // 만들려는 숫자가 스택의 top에 올 때까지 push
    while (currentNumber <= makeNumber) {
      stack.push(currentNumber);
      result.push("+");
      currentNumber += 1;
    }

    // 스택의 top에 만들려는 숫자가 있으면 pop
    if (stack[stack.length - 1] === makeNumber) {
      stack.pop();
      result.push("-");
      // 만들 수 없는 경우
    } else {
      result = ["NO"];
      break;
    }
  }

  console.log(result.join("\n"));