백준 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️⃣위 전체 코드