17299. 오등큰수

우선, n이 백만이여서 O(n2)으로 풀면 시간초과에 걸린다.
아래는 시간초과 풀이이다.

import sys;input=sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
from collections import Counter
c = Counter(a)
most_common = c.most_common()[0][0]
for i in range(n):
  if a[i] == most_common:
    print(-1, end=' ')
    continue

  for j in range(i+1, n):
    if c[a[j]] > c[a[i]]:
      print(a[j], end= ' ')
      break

리스트를 순회하면 안될 것 같다. 어떻게 하면 순회를 안하고 한번에 모두 해결할 수 있을까? 아래와 같이 더 큰걸 만날 때 까지 스택에 넣었다가 더 큰 빈도의 숫자를 만나면 pop해주면서 리스트에 할당해준다.

from collections import Counter
from sys import stdin

n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))
nums_count = Counter(nums)
result = [-1] * n
stack = [0]

for i in range(1, n):
    while stack and nums_count[nums[stack[-1]]] < nums_count[nums[i]]:
            result[stack.pop()] = nums[i]
    stack.append(i)

print(*result)

아래는 자바스크립트 풀이이다.

const line = require("fs").readFileSync("/dev/stdin", "utf8");
const input = line.trim().split("\n");

const N = Number(input[0]);
const A = input[1].split(" ").map((x) => Number(x));

const stack = [];
const ans = new Array(N).fill(-1);
const cnt = {};

A.forEach((x) => (cnt[x] ? (cnt[x] += 1) : (cnt[x] = 1)));

for (let i = 0; i < N; i++) {
  while (stack.length && cnt[A[i]] > cnt[A[stack[stack.length - 1]]]) {
    ans[stack.pop()] = A[i];
  }
  stack.push(i);
}

console.log(ans.join(" "));