알고리즘 기초 - 오큰수

백준 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

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

---

📝풀이 과정

강조 또 강조하지만 문제의 정의부터 꼼꼼히 분석해야한다.

문제에서 주어진 오큰수의 정의는 Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수이다.

그렇다면 요소의 오른쪽을 탐색하면서 가장 왼쪽에 있는 수가 무슨 값인지를 나타내면 된다.

 

나이브하게 생각하면 이중for문을 이용해서 오른쪽 요소 중 가장 왼쪽에 있는 값을 탐색하는 방법이 있다.

하지만 시간복잡도는 O(N^2)이다. 입력값의 범위로 봤을 때 분명히 시간초과가 날 것이다.

골드레벨은 그리 만만하게 조건을 주지 않는다.

 

🤔반대로 생각해보기

예를 들어 3, 5, 2, 7이라는 수열이 주어졌다.

요소를 하나씩 탐색하며 오큰수를 찾는 것이 아니라, 해당 요소를 오큰수로 가지는 값이 있는지를 확인해보자.

3을 오큰수로 갖는 수는 없다. 왜냐하면 3의 왼쪽에는 어떤 값도 존재하지 않기 때문이다. 

5를 오큰수로 갖는 값은 3이다. 2를 오큰수로 갖는 값도 없다. 7을 오큰수로 갖는 값은 5와 2이다.

따라서 오큰수를 표현하면 다음과 같다.

3, 5, 2, 7 ➡ 5, 7, 2, ❌

마지막 요소는 무조건 오큰수를 가질 수 없다.

 

하지만 위의 방식으로도 시간복잡도를 크게 줄일 수 없다. 왜냐하면 오큰수를 이미 찾은 요소도 순회를 하기 때문이다.

그렇다면 이미 오큰수를 찾은 값은 순회하지 않으면 시간복잡도를 줄일 수 있다.

그 방법으로 스택을 사용하는 것이다.

스택을 사용해야겠다고 아이디어를 떠올리는 것이 이 문제의 난이도를 높였다...😂

 

🧩스택을 사용한 풀이

오큰수는 오른쪽에 있는 요소들 중 가장 왼쪽에 있는 값이다. 즉, 가장 먼저 나오는 자신보다 큰 수가 되는 셈이다.

따라서 스택에 요소들을 넣으면서 스택의 맨 위 요소와 비교해서 큰 값이 나오면 그 값을 오큰수로 하면 된다.

그림으로 표현해보자. 수열은 [3, 5, 2, 7] 을 예시로 든다.

🛠코드

let [n, arr] = require('fs').readFileSync(0).toString().trim().split('\n');
arr = arr.split(' ').map(Number);

function solution(arr) {
  const stack = [];
  const result = Array.from({ length: arr.length }, () => -1);
  for (let i = 0; i < arr.length; i++) {
    const topIdx = stack[stack.length - 1];
    if (arr[topIdx] < arr[i]) {
      while (arr[stack[stack.length - 1]] < arr[i]) {
        const idx = stack.pop();
        result[idx] = arr[i];
      }
      stack.push(i);
    } else stack.push(i);
  }
  return result.join(' ');
}

console.log(solution(arr));

 

느낀점

스택의 활용은 어디까지인가. 또 한번 좌절을 느낀다...😢