알고리즘 기초 - 오등큰수 (백준 17299)

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1

7
1 1 2 3 4 2 1

예제 출력 1

-1 -1 1 2 2 1 -1

---

오큰수 문제의 심화버전이다.

마찬가지로 O(N^2)이 되면 시간초과가 나오므로 O(N)이 되도록 로직을 짜야한다.

문제에서 알 수 있듯이 오등큰수는 자신보다 수열에서 등장한 횟수가 많은 수 중에서 가장 왼쪽에 있는 수이다.

따라서 우선 수열을 이루는 요소들의 갯수를 해시맵을 이용해 카운팅한다.

그리고 수열을 스택에 하나씩 담으면서 오등큰수인지를 확인하고 맞다면 스택을 팝한다.

 

let [n, a] = require('fs').readFileSync(0).toString().trim().split('\n');
n = Number(n);
a = a.split(' ').map(Number);
let m = new Map();
let stack = [];
let ret = Array.from({ length: n }).fill(-1);

function solution() {
  a.forEach((n) => {
    if (m.has(n)) m.set(n, m.get(n) + 1);
    else m.set(n, 1);
  });
  a.forEach((n, idx) => {
    while (stack.length && m.get(a[stack[stack.length - 1]]) < m.get(n)) {
      ret[stack[stack.length - 1]] = n;
      stack.pop();
    }
    stack.push(idx);
  });
  return ret.join(' ');
}

console.log(solution());

 

  a.forEach((n, idx) => {
    while (stack.length && m.get(a[stack[stack.length - 1]]) < m.get(n)) {
      ret[stack[stack.length - 1]] = n;
      stack.pop();
    }
    stack.push(idx);
  });

이 부분이 수열을 순회하며 스택에 담는 과정이다. 스택에는 수열의 인덱스를 담는다.

스택이 비어있지 않고 오등큰수를 찾았다면 스택에 담겨있는 인덱스에 접근해 오등큰수를 넣어준다. 그리고 팝한다.

계속 오등큰수인지를 비교해서 맞다면 같은 과정을 반복한다. 아니라면 스택에 인덱스를 푸쉬한다.