🔍 2493번: 탑
클릭해서 문제 전체 보기🔼
📖 풀이 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, tops] = fs.readFileSync(filePath).toString().trim().split("\n");
let topArr = tops.split(" ").map((v) => +v);
let tmpTopArr = [topArr.shift()]; // = stack Top
let tmpIdx = [1]; // = stack Top Idx
let result = [0];
topArr.splice(0, 0, "null", "null");
for (i = 2; i < topArr.length; i++) {
while (tmpTopArr.length > 0) {
let lastTop = tmpTopArr.pop();
let lastIdx = tmpIdx.pop();
if (topArr[i] <= lastTop) {
result.push(lastIdx);
tmpTopArr.push(lastTop);
tmpIdx.push(lastIdx);
tmpTopArr.push(topArr[i]);
tmpIdx.push(i);
break;
}
}
if (tmpTopArr.length == 0) {
result.push(0);
tmpTopArr.push(topArr[i]);
tmpIdx.push(i);
}
}
console.log(result.join(" "));
📢 풀이 설명
문제 내용 해석
뒤에서 앞으로 레이저를 쏘는데 자신보다 높은 탑이 있으면 레이저가 그 탑에 도달하므로 그 탑의 번호를 출력한다. 앞에 자신보다 높은 탑이 없다면 0을 출력한다.
풀이 내용은 입력된 탑들을 순서대로 앞에서 뒤로 확인하며, 해당 탑 앞에 더 높은 탑이 있는지 확인한다. 확인하는 방법은 tmpTopArr(=stack)을 보면 된다.
- 만약 자신보다 높은 탑이 있다면 결과에 자신보다 높은 탑의 순서를 넣고,
tmpTopArr(=stack)에 자신의 탑 높이도 넣고, Idx 배열에도 자신의 순서를 넣는다.
자신의 순서도 넣는 이유는, 뒤에 나올 탑들이 자신보다 낮을 수도 있기 때문이다. - 자신보다 높은 탑이 없을 경우 결과에 0을 넣고,
tmpTopArr(=stack)에 자신의 높이를 넣고, Idx배열에도 자신의 순서를 넣어둔다.
자신보다 높은 탑이 스택 아래에 쌓여있을 수도 있기 때문에 pop으로 스택을 하나씩 지워가며 확인한다. 그렇게 스택이 비어서 자신보다 높은 탑이 없음을 확인한다.
맨 첫번째 탑은 없으므로 처음부터 tmpTopArr(=stack), tmpIdx(=stack Idx) 배열에 해당 탑 높이, 0을 뽑아서 넣어두고 시작한다.
이렇게 되면 입력된 2번째 탑의 idx가 0이 되기때문에 splice를 이용해 앞에 2개의 null 값을 넣어준다. 그렇게 되면 탑 번호와 idx가 맞춰진다.
그 후 for문을 돌며 탑을 순서대로 확인한다.
이 문제는 탑들의 높이를 저장하면서, 저장된 탑보다 높은 탑이 나오면 갈아끼우는 방식으로 진행한다.
따라서 스택 알고리즘을 사용했다.
📖 또 다른 풀이 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, tops] = fs.readFileSync(filePath).toString().trim().split("\n");
let topArr = [0, ...tops.split(" ").map((v) => +v)];
let stack = [];
let result = [];
let peek = [];
label: for (i = 1; i < +n + 1; i++) {
let curTop = topArr[i];
while (stack.length > 0) {
if (curTop > peek[0]) {
stack.pop();
peek = stack[stack.length - 1];
} else {
result.push(peek[1]);
stack.push([curTop, i]);
peek = [curTop, i];
continue label;
}
}
result.push(0);
stack.push([curTop, i]);
peek = [curTop, i];
}
console.log(result.join(" "));
📢 풀이 설명
통과한 후 다른 풀이들을 보며 한번 더 풀어봤다.
내가 푼 것과 전체적인 로직은 같고, 차이점은 2차원 배열 peek과 label을 사용한 것, 조건문의 등호를 반대로 쓴 것이다.
더 자세히 설명하면, 먼저 idx와 탑의 순서를 맞추기 위해 topArr에 맨 앞에 0값을 넣어줬다.
그리고 매번 stack의 맨 마지막 값을 확인하는 번거로움을 피하기위해 peek을 만들어 넣어줬다.
stack 배열이 빈 것을 확인하기 위한 조건문을 사용하지 않고, label을 사용해 원하는 곳으로 돌아가게 만들었다.
