[boj] 17298. 오큰수 (node.js)

문제 요약

[boj] 17298. 오큰수 (node.js)

• 오큰수 (NGE, 해당 수의 오른쪽 수 중 그 수보다 크면서 가장 가까운 수)를 찾는 문제

풀이

내 첫 풀이

function NGE() {
  // 스택: LIFO
  let stack = [];
  let curIdx = 0;

  while (true) {
    let len = stack.length;
    // 스택이 비었거나 스택에 마지막으로 넣은 숫자보다 작거나 같은 수면
    // 그 수의 인덱스를 스택에 넣기
    if (curIdx == N) {
      popStack();
      results[N - 1] = -1;
      if (stack.length) stack.forEach((idxElem) => (results[idxElem] = -1));
      return;
    }
    if (len == 0 || arr[curIdx] <= arr[stack[len - 1]]) {
      stack.push(curIdx);
      curIdx++;
    } else {
      popStack(); // 스택에 들어있는 수를 확인해서 조건에 맞으면 뽑아낸다
    }

    function popStack() {
      // 스택에 있던 수가 curIdx 번째 수보다 작으면 추출
      while (arr[stack[stack.length - 1]] < arr[curIdx]) {
        let idx = stack.pop();
        // 추출된 수의 NGE는 curIdx번째 값
        results[idx] = arr[curIdx];
      }
    }
  }
}

• 모든 인덱스를 순회하며 값을 확인해서 스택에 push, pop 여부를 결정하므로, for 문 내부에 로직을 구성할 수 있다.
• 따라서 for 문에서 현재 확인할 인덱스(curIdx)를 순회한다.
  • stack 수정 조건
    • stack에서 pop: 해당 수가 스택 맨 뒤의 수보다 큰 경우 일어난다.
    • stack에 push: 항상 일어난다.
  • 위 두 가지 조건에 의해 스택 내부이 값이 변경된다.
  • pop은 스택의 맨 뒤 숫자가 curIdx의 수보다 작은 경우만 성립한다. 해당 조건이 만족하지 않을 때까지 계속 while 문을 돌며 pop하고 pop된 인덱스의 오큰수는 curIdx의 값이 된다.
  • pop 여부와 무관하게, 조건에 대한 판단 이후 push는 항상 일어나므로 push문을 조건문 다음에 넣는다.

개선한 풀이 - 다른 사람의 풀이 참고

function NGE() {
  let stack = [];
  for (let curIdx = 0; curIdx < N; curIdx++) {
    if (arr[curIdx] > arr[stack[stack.length - 1]]) {
      while (arr[stack[stack.length - 1]] < arr[curIdx]) {
        results[stack.pop()] = arr[curIdx];
      }
    }
    stack.push(curIdx);
  }
}

• 다른 사람의 풀이
• 동일한 알고리즘인데, 훨씬 간결하게 짤 수 있다! 이 풀이를 참고해서 다시 풀어봤다.

마무리

• 생각보다 어려웠고, 자료구조가 알고리즘에 유용하게 쓰인다는 말을 특히 '스택'문제를 풀며 많이 느꼈다. 자주 사용하는 Queue나, 그래프 등의 자료구조는 익숙했지만 스택 문제를 처음 접근하게 되니, 문자열로 연관지어 생각하게 되었다. 알고리즘 스터디원 분께서 LIFO 자료구조의 특징을 유념해 생각한다면, 스택을 떠올리기 좀 더 수월할 수 있다는 의견을 주셨다. 자료구조의 특징을 떠올리며, 문제 풀이해서 한 번쯤 고민해보는 습관을 갖자.

전체 코드

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

const solution = () => {
  const N = Number(input());
  let arr = input().split(" ").map(Number);
  let results = new Array(N).fill(-1);
  NGE();
  console.log(results.join(" "));

  function NGE() {
    let stack = [];
    for (let curIdx = 0; curIdx < N; curIdx++) {
      if (arr[curIdx] > arr[stack[stack.length - 1]]) {
        while (arr[stack[stack.length - 1]] < arr[curIdx]) {
          results[stack.pop()] = arr[curIdx];
        }
      }
      stack.push(curIdx);
    }
  }
};

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});