[백준] 17299. 오등큰수 풀이 / Python, JavaScript

17299번: 오등큰수

 

이 문제는 오큰수 문제와 크게 다른 것은 없고 조건식만 조금 바꿔주면 동일한 문제입니다.

[백준] 17298. 오큰수 풀이 / Python, JavaScript

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
table = list(map(int, input().split()))
s = []
c_table = [0] * (max(table) + 1)
result = [-1 for _ in range(n)]
for i in table:
    c_table[i] += 1
for i in range(n):
    while s and c_table[table[s[-1]]] < c_table[table[i]]:
        result[s.pop()] = table[i]
    else:
        s.append(i)
print(*result)

작성 코드 (.js)

function solution(n, numbers) {
  const result = Array(n).fill(-1);
  const s = [];
  const cTable = Array(Math.max(...numbers) + 1).fill(0);

  numbers.forEach((number, i) => (cTable[number] += 1));
  numbers.forEach((number, i) => {
    while (s.length && cTable[numbers[s[s.length - 1]]] < cTable[number]) {
      result[s.pop()] = number;
    }
    s.push(i);
  });
  return result;
}

 

구현로직 (스택)

똑같이 스택을 사용해주고 다른 조건을 위해 카운트 테이블을 만들어줍니다. 미리 각 수열의 원소의 수를 C테이블에 입력해두고 오큰수 조건과 다르게 현재 확인중인 원소의 개수가 스택의 최상단 원소의 개수보다 작아질 때까지 스택에서 원소를 꺼내 해당 원소의 인덱스 자리에 오등큰수를 입력합니다.

 

스택의 동작 방식은 오큰수 풀이에서와 동일합니다.