[백준] 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)을 공백으로 구분해 출력한다.

풀이

const oKeun = () => {
  const fs = require("fs");
  let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  const len = parseInt(input[0]);
  const arr = input[1].split(" ").map((n) => {
    return parseInt(n);
  });
  let stack = [];
  let arrReturn = [];

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

oKeun();

반성회

// ======= 입력값 =======
4
3 5 2 7

// ======= 동작 =======
0번째 루프
현재 원소: 7
스택: []
// 스택이 비어 있으므로 아무것도 pop하지 않는다
// 7보다 오른쪽에 있는 수가 없으므로 7에 대한 오큰수는 -1이다
정답 배열: [-1]

1번째 루프
현재 원소: 2
스택: [7]
// 스택은 비어있지 않지만, 7은 2보다 크므로 아무것도 pop하지 않는다
// 스택의 top 값이 7이므로 2에 대한 오큰수는 7이다
정답 배열: [-1, 7]

2번째 루프
현재 원소: 5
스택: [7, 2] => [7] // stack.pop();
// 스택이 비어있지 않고, 2는 5보다 작으므로 2를 pop한다
// 따라서 스택의 top 값이 7이 되므로 5에 대한 오큰수는 7이다
정답 배열: [-1, 7, 7]

3번째 루프
현재 원소: 3
스택: [7, 5]
// 스택이 비어있지 않지만, 5는 3보다 크므로 아무것도 pop하지 않는다
// 스택의 top 값이 5이므로 3에 대한 오큰수는 5이다
정답 배열: [-1, 7, 7, 5]

// ====== 출력 ======= 
정답 배열: [-1, 7, 7, 5]
정답 배열의 역순: [5, 7, 7, -1]
출력: 5, 7, 7, -1
// 정답 배열에 값을 넣을 때, 원본 수열의 오른쪽 값부터 오큰수를 넣었으므로
// 순서를 역순으로 바꾸어 주어야 함

1. 수열은 오른쪽 끝에서 왼쪽으로 검사한다스택에 들어가는 순서는 오른쪽 → 왼쪽이므로, 스택에서 빠져나오는 순서는 기준 원소에서 가장 왼쪽에 있는 수부터 빠져나오게 된다
2. 수열의 원소를 하나씩 스택에 넣되, 기준 원소의 오른쪽에 있는 수들 중 기준 원소보다 크면서 가장 왼쪽에 있는 수를 알아내야 하므로 수열의 오른쪽부터 하나씩 스택에 push하여 그 다음 원소의 오른쪽에 있는 수들이 스택에 들어있도록 한다
3. 스택의 길이가 0 이상이고, 스택의 top 값이 현재 숫자보다 작거나 같다면 pop한다 ⇒ 반복
4. 스택에서 기준 원소의 바로 왼쪽에 있는 숫자부터 pop되므로 이런 식으로 하나씩 작은 숫자들을 지워가다 보면 결국 기준 원소보다 크면서 가장 왼쪽에 있는 숫자가 스택의 top에 남아있게 된다
5. 반복문을 빠져나왔을 때 스택이 비어있다면, 기준 원소의 오른쪽에는 기준 원소보다 큰 수가 없다는 뜻이므로 정답 배열에 -1을 push한다
6. 스택이 비어있지 않다면, 정답 배열에 스택의 top 값을 push한다
7. 현재 기준 원소를 스택에 push하고, 다음 원소 (기준 원소보다 왼쪽에 있는 원소) 로 넘어가 2 ~ 3을 반복한다
8. 정답 배열을 출력하되, 역순으로 출력한다
9. 수열의 오른쪽에서 왼쪽으로 검사했으므로, 수열의 맨 왼쪽 정답부터 출력하려면 정답 배열을 뒤집어야 함