백준 js 17298: 오큰수
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
예제 입력 1
4 3 5 2 7
예제 출력 1
5 7 7 -1
풀이
배열 input에 대해서 x[i] 보다 오른쪽에 있는 수 중 가장 가까운 input[i]보다 큰수를 찾으면 된다.
가장 가까운 수를 찾기 위해서는 stack을 사용한다.
input를 하나씩 돌면서, stack에 input의 index를 push해주는데,
for (let i = 0; i < input.length; i++) {
stack.push(i);
}이 스택에 쌓인 i는 input[i] 보다 큰 수를 아직 찾지 못한 input 인덱스들이 모여있다.
let result = new Array(input.length).fill(-1);
for (let i = 0; i < input.length; i++) {
`
1️⃣stack에 수가 있으면 (더 큰 수를 찾지 못한 수가 있다면)
stack에 있는 값을 인덱스로 하는 Input[i]와 현 i를 인덱스로 갖는 input[i]를 비교
input[i]가 더 크다면 stack에 있는 값들을 pop()하고
result[stack 값]들에 input 현 i를 인덱스로 가지는 값들을 push한다.
`
/*2️⃣*/stack.push(i);
}이 과정을 구체적인 예를 들어보면,
3 5 2 7이라는 수가 주어졌다고 하자.
+ result는 input.length 만큼 -1로 초기화 되어 [-1, -1, -1, -1] 이다.
i = 0일 때,
1️⃣
stack = [] 이므로 아무 것도 하지 않는다
2️⃣
stack = [0]이 된다.
i = 1일 때,
1️⃣
stack = [0] 이므로
input[0]과 input[1] 비교한다.
input[0] < input[1] 이므로
stack.pop()을 한다
stack = [], result[5([input[0]), -1, -1 , -1]이 된다.
2️⃣
stack = [1]이 된다.
i = 2일 때,
1️⃣
stack = [1] 이므로
input[1]과 input[2] 비교한다.
input[1] < input[2] 성립하지 않으므로
아무 것도 하지 않고 넘어간다.
2️⃣
stack.push(i)해서
stack = [1, 2]이 된다.
i = 3일 때,
1️⃣
stack = [1, 2] 이므로
(input[1], input[2])과 input[3] 비교한다.
input[2] < input[3] 이므로
stack.pop()을 한다
stack = [1], result[5([input[0]) , 7([input[3]), -1, -1]이 된다.
input[1] < input[3] 이므로
stack.pop()을 한다
stack = [], result[5([input[0]) , 7([input[3]), 7([input[3]), -1], 이 된다.
2️⃣
stack = [3] 되고 루프가 끝난다.
즉, 스택을 이용해서 루프문 안에서 스택을 쌓는데, x보다 큰 수가 나오면 바로 x의 index를 갖는 result에 나보다 큰 값을 push해준다
x보다 큰수가 나올 때까지 스택에 넣고 아무 것도 하지 않다가.
이렇게 스택을 이용해서 스택에 있는 수와
루프에서 가장 최근에 조건이 맞는 부분과 비교하여
바로 push, pop하므로
오큰수를 보장할 수 있다.
전체코드
시도
3가지 방법으로 시도해봤는데,
1️⃣stack.top() + stack.pop()이 아니라 for문 사용해서 stack하나씩 비교하기 -> 시간 초과
let stack = [];
let result = new Array(input.length).fill(-1);
for (let i = 0; i < input.length; i++) {
const ssize = stack.length;
for (let j = ssize - 1; j >= 0; j--) {
if (input[i + 1] > input[stack[j]]) {
result[stack[j]] = input[i + 1];
stack.pop();
}
}
stack.push(i);
}
console.log(result.join(" "));2️⃣for문이 아니라 map 사용해서 루프문 사용하기 -> +4ms
let result = new Array(input.length).fill(-1);
let stack = [];
input.map((x, i) => {
while (stack.length && input[stack[stack.length - 1]] < x) {
result[stack.pop()] = x;
}
stack.push(i);
});
console.log(result.join(" "));3️⃣위 전체 코드