[JS] 백준 2493번 : 탑 - 자료구조, 스택

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

2493번: 탑

 

📋풀이방법

1. 주어진 탑의 높이를 차례로 순회하면서 스택의 top부분과 비교한다.

 - 1. 스택의 top의 높이가 더 작을 경우 스택의 top부분이 검사하는 높이보다 커질 때까지 pop하면서 반복한다.

 - 2. 만약 스택의 top높이가 더 클 경우 정답에 해당 높이의 인덱스를 넣고, 검사하는 높이를 스택에 넣어준다.

 - 3. 만약 스택이 비어있을 경우 검사하는 높이의 값을 스택에 넣어준다.

 

그림으로 풀어보자

 

1. 스택이 비어있을 경우

-값을 그냥 넣어주면 된다.

2. 스택의 top값이 검사하는 값보다 작을 경우

-스택의 top값이 없거나 top값이 검사하는 값보다 커질 때까지 pop해준다.

  - pop의 반복으로 스택의 top값이 없다면 stack에 검사하는 값을 넣어주고

  - pop의 반복으로 스택의 top값이 검사하는 값보다 커졌을 경우 해당 top의 인덱스 값을 result에 기록한다.

- 이 때 result배열은 0으로 초기화했으므로 6과 9는 0으로 기록되어진다.

3. 스택의 top값이 검사하는 값보다 클 경우

-top값의 인덱스를 result에 기록한다.

-아래와 같이 5와 7은 7이 크므로 5는 pop하고,

-9와 7은 9가 크므로 stack에 값을 넣어주고 result에 top에있던 인덱스를 result에 기록해준다.

 

 

🤟내 제출

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 = Number(input[0]);
let arr = input[1].split(" ").map((v, idx) => [Number(v), idx + 1]);

let stack = [];
let top = stack.length - 1;
let result = Array.from({ length: N }, () => 0);

for (let i = 0; i < arr.length; i++) {
  if (stack.length > 0 && stack[stack.length - 1][0] < arr[i][0]) {
    while (stack.length > 0 && stack[stack.length - 1][0] < arr[i][0]) {
      stack.pop();
    }
  }
  if (stack.length > 0 && stack[stack.length - 1][0] > arr[i][0]) {
    result[i] = stack[stack.length - 1][1];
    stack.push(arr[i]);
  } else {
    stack.push(arr[i]);
  }
}
console.log(result.join(" "));

 

 

💢어려웠던 점

1. 아래와같이 코드를 작성하면 10의자리 숫자부터 값이 이상하게 들어가게된다.

// 10
// 6 1 8 5 9 2 4 3 7 10

let arr = input[1].split(" ").map((v, idx) => [Number(...v), idx + 1]);

/*
[
  [ 6, 1 ], [ 1, 2 ],
  [ 8, 3 ], [ 5, 4 ],
  [ 9, 5 ], [ 2, 6 ],
  [ 4, 7 ], [ 3, 8 ],
  [ 7, 9 ], [ 1, 10 ] // <- [10,10]이 아닌 [1,10]이 들어감
]
*/

let arr = input[1].split(" ").map((v, idx) => [Number(v), idx + 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 = Number(input[0]);
let arr = input[1].split(" ").map((v, idx) => [Number(v), idx + 1]);

let stack = [];
let result = [];

for (let i = 0; i < N; i++) {
  if (stack.length === 0) {
    stack.push(arr[i]);
    result.push(0);
    continue;
  }
  if (stack[stack.length - 1][0] < arr[i][0]) {
    while (stack.length > 0) {
      if (stack[stack.length - 1][0] > arr[i][0]) {
        break;
      } else {
        stack.pop();
      }
    }
    result.push(stack.length == 0 ? 0 : stack[stack.length - 1][1]);
    stack.push(arr[i]);
  } else {
    result.push(stack[stack.length - 1][1]);
    stack.push(arr[i]);
  }
}
console.log(result.join(" "));