[JS] 백준 17298번 - 오큰수 - 스택, 자료구조

https://www.acmicpc.net/status?user_id=oridori2705&problem_id=17298&from_mine=1 

채점 현황

 

 

📋풀이방법

1. 스택을 이용해서 문제를 풀어야한다.

2. 위 그림대로 주어진 배열의 숫자를 하나씩 검사한다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, temp] = input;
N = Number(N);

const arr = temp.split(" ").map(Number);
let stack = [];
let answer = Array.from({ length: N }, () => -1);

for (let i = N - 1; i >= 0; i--) {
  while (stack.length != 0 && stack[stack.length - 1] <= arr[i]) {
    stack.pop();
  }

  if (stack.length == 0) {
    answer[i] = -1;
  } else {
    answer[i] = stack[stack.length - 1];
  }

  stack.push(arr[i]);
}
console.log(answer.join(" "));

 

 

💢어려웠던 점

1. 스택을 이용한다는 것을 파악하지 못했다

- 그저 for문으로 검사하는 문제인지 아니면 DP처럼 효율적으로 풀이하는 문제인지에 대해 생각하느라 시간을 소모했다.

- 스택을 이용함으로써 오른쪽에서 큰 수이면서 가장 가까운 수임을 빠르게 찾을 수 있다.

2. 주어진 숫자의 배열을 뒤에서 부터 검사하는 것을 파악하지 못했다.

- 문제의 가장 중요한 점인데 오른쪽에서 가장 큰 수이므로 배열의 마지막 숫자부터 검사를 진행해야하는 것이였다.

- 이 오른쪽에서 가장 큰 수라는 조건을 잘 생각해야했다.

3. 오른쪽에서 값이 크면서 가장 가까운 수라는 조건을 빠르게 파악하지 못했다.

- 이 조건이 스택을 사용하는 이유였다.

 

- 스택이 비어있다면 => 오큰수가 없는 것

- 스택이 비어있지 않다면 => 오큰수를 마지막 부분부터 확인함

  1. 스택의 마지막 부분의 값이 검사하는 숫자보다 크다면 => 오큰수를 발견함

  2. 스택의 마지막 부분의 값이 검사하는 숫자보다 작거나 같다면 => 오큰수가 아님, 또한 pop()으로 그 수를 스택에서 제외

   => 일단 먼저 마지막 부분을 검사하는 이유는 => 가장 가까운 수

   => 작거나 같은 숫자를 제외하는 이유는

      => 작거나 같다면 이후 숫자에서도 쓸모가 없는 숫자임

          => 제외하는 숫자가 아닌 현재 검사하는 숫자가 이후 숫자의 오큰수가 됨(이유는 당연히 가장 가까우니까)

- 이 두 조건을 통해 정답을 넣고, 검사하던 값을 스택에 넣어준다.->이후 검사하는 숫자를 위해

3. 만약 오큰수를 찾았을 때 답을 어떻게 기입할 것인지에 대해서 빠르게 풀어내지 못했다.

-오큰수를 while을 통해 찾아냈다면 그 수를 어떻게 정답에 올바른 인덱스로 넣어야할까에 생각하느라 시간을 소모했다.

-그저 현재 검사하는 값의 인덱스를 활용하면 됐었다.