BOJ 17298번 오큰수 JavaScript 풀이
Stack 자료구조 문제다. 내가 처음 시도했던 풀이는 스택을 제대로 활용하지 못한 풀이였다. 따라서 시간 초과로 인해 통과할 수 없었다. 스택을 제대로 이해하여 시간복잡도를 줄이는 풀이를 사용해야 통과할 수 있었다.
문제
잘못된 접근
[1] 마지막 원소를 제외한 수열(arr)의 원소를 순회하면서 (마지막 원소의 오큰수는 존재하지 않는다)
[2] 다시 해당 원소의 바로 다음 원소부터 배열의 끝까지 탐색하여
[3] 자기 자신보다 큰 수가 나오면 그것이 오큰수이기 때문에 스택에 추가한 뒤 즉시 탐색을 멈추고(break)
[4] 자기 자신보다 큰 수가 없으면 스택에 추가한다.
[5] [2]번에서의 순회가 끝났는데 스택이 비었다면 정답 배열에 -1을, 그렇지 않다면 스택에 들어있는 수를 정답 배열에 추가했다.
[6] 마지막 원소의 오큰수는 언제나 없으므로 정답 배열에 -1을 추가한다.
const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);
const arr = input[1].split(" ").map(e => Number(e));
let answer = [];
let stack = [];
for(let i=0; i<N-1; i++) {
for(let j=i+1; j<N; j++) {
if(arr[i] < arr[j]) {
stack.push(arr[j]);
break;
}
}
if(stack.length) answer.push(stack.pop());
else answer.push(-1);
}
answer.push(-1);
console.log(answer.join(" "));스택이라는 자료구조의 의미를 제대로 살리지 못한 이 풀이의 시간복잡도는 O(N*N)이다.
모든 원소에 대해서, 다시 그 다음 원소부터 배열의 끝까지 탐색해야 하기 때문이다.
Stack 활용하기
[1] 정답 배열을 원소의 개수만큼 -1로 초기화한다.
[2] 수열을 순회하면서 이번에는 원소의 인덱스를 stack에 담는다.
[3] 만약 순회 중인 원소가 stack의 top 인덱스에 해당되는 원소보다 작다면, 그 수는 stack의 top에 해당되는 수의 오큰수가 아니기에 인덱스를 stack에 추가한다.
[4] 반대로 순회 중인 원소가 크다면, 그 수는 이때까지 stack에 쌓여있는 인덱스에 해당하는 수들의 오큰수라는 뜻이다. 따라서 자신을 오큰수로 갖지 않는 즉, 자신보다 큰 수에 해당하는 인덱스까지 stack을 pop하고, 마지막으로 자신의 인덱스를 stack에 추가한다.
[5] 이때 stack에서 pop 되는 인덱스에 해당되는 정답 배열의 자리에 위치한 -1을 [4]에서 찾은 오큰수로 교체한다.
const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);
const arr = input[1].split(" ").map(e => Number(e));
let answer = Array.from({length:N}, () => -1);
let stack = [0];
for(let i=1; i<N; i++) {
while(arr[stack[stack.length-1]] < arr[i] && stack.length) {
answer[stack.pop()] = arr[i];
}
stack.push(i);
}
console.log(answer.join(" "));(첫 번째 원소의 인덱스를 stack에 추가한 상태로 순회를 시작했다)
위의 방법을 사용하여 -1로 초기화 되어 있던 정답 배열에서 오큰수가 존재하는 수만 해당 오큰수로 바꿔주었다. stack 자료구조를 활용하여 시간복잡도를 O(N)으로 줄일 수 있었던 것 같다.
이 풀이는 메모리 200868KB, 시간 888ms 정도로 통과가 된다.
최초에 문제를 접했을 때는 완전 탐색 방법을 사용하는 쉬운 문제라고 생각했다. 하지만 stack의 의미를 제대로 이해하고 사용하지 않으면 풀 수 없는 문제였다. stack에 원소를 넣다 빼는 게 문제에서 무엇을 의미하는지, stack에 무엇을 넣을 것인지, 잘 고민해봐야 했다..
풀이에서 잘못된 부분이 있거나, 더 좋은 풀이가 있다면 적극적으로 제보 부탁드립니다!