[백준] 17299번 오등큰수 Python 풀이

서론

17298번인 오큰수 문제와 매우 비슷하다.
오큰수의 문제 접근 방식에서 한 단계 더 나아가면 된다.
아직 오큰수 문제를 풀어보지 않았다면
그 문제부터 풀고 오등큰수를 시도해보는 것이 좋다!

(이전 글) 오큰수 문제 풀이 참고 ⬇️
https://velog.io/@okxooxoo/백준-17298번-오큰수-Python-풀이

처음 풀이 (시간 초과)

import sys
input = sys.stdin.readline

N = int(input())
lst = input().split()

count = []
for i in lst:
    count.append(lst.count(i))

stack = []
result = [-1] * N
for i in range(N):
    while stack and count[i] > count[stack[-1]]:
        result[stack.pop()] = lst[i]
    stack.append(i)

print(*result)

사고의 과정 💭

오등큰수는 자신보다 많이 등장하는 즉, 빈도수가 높은 오른쪽의 숫자를 찾는 문제이다.

1 1 2 3 4 2 1

만약 위와 같은 수열이 있을 때 index = 2 에 위치하는 숫자 2는 위 수열에서 2번 등장하기 때문에 빈도수가 2이다.
2보다 더 많이 등장하는 숫자로는 1이 있다.
또한 2의 오른쪽에 1이 등장하기 때문에 2의 오등큰수는 1이 된다.

따라서 숫자가 얼마나 등장하는지 카운트하는 것이 이 문제의 핵심이구나!
라고 생각했다 🥸
이를 위해 리스트 안의 특정 원소의 개수를 세어주는 파이썬 내장 함수인 count()를 이용하였는데 시간 초과가 발생하였다❗️

왜인가 하니 count() 함수 자체의 시간복잡도가 O(n)이라고 한다.

따라서 리스트를 순회하며 각 원소당 count() 함수를 사용하는 것은 O(n^2)의 시간복잡도이니 시간 초과가 발생할 수밖에 없었다.

문제 접근 💡

step ➊

그러면 count() 함수를 사용하지 않고 어떻게 숫자의 빈도수를 셀 수 있을까?
힌트는 문제의 입력 조건에 있다!

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

수열에 등장하는 숫자인 N의 범위는 백만(1,000,000) 이하이다.
따라서 백만의 크기를 가지는 리스트를 하나 생성한다.
이 리스트의 index에 대응되는 값은 index의 빈도수가 될 것이다.
(⬆️ 이 리스트의 이름을 count = [] 라고 이름 붙이겠다.)

예시를 들어보자.
for문을 이용하여 입력받은 수열을 순회한다.
만약 현재 원소가 2라면 count[2] += 1 을 한다.
만약 현재 원소가 5라면 count[5] += 1 을 한다.

어차피 입력되는 숫자의 범위는 1부터 백만이기 때문에
백만 크기의 count라는 리스트를 생성하고
이를 이용하여 숫자의 빈도수를 카운트할 수 있다.

(사실 백준 10989번 카운팅 정렬 문제를 풀어보지 않았다면 위의 발상은 떠올리기 쉽지 않다 💭)

카운팅 정렬이란?
숫자 배열의 최솟값과 최댓값의 범위가 백만 이하이고
중복된 숫자가 많다면 아주 빠르게 정렬할 수 있는 알고리즘이다.

step ➋

(여기서부터는 오큰수의 코드와 거의 동일하다.)

이처럼 count 리스트를 이용하여 모든 숫자의 빈도수를 세주었다면
스택(stack)을 활용하여 오등큰수를 찾지 못한 숫자들을 스택에 보관한다.

1 1 2 3 4 2 1

사용자로부터 위의 숫자들을 입력받았다고 가정한다.

for문을 통해 입력받은 숫자의 개수(7)만큼 반복한다.
for문에서 한번 반복이 실행될 때 하는 일은 크게 2가지이다.

1️⃣ 리스트의 현재 원소와 스택의 상단에 있는 원소의 빈도수를 비교한다.
이때 각 원소의 빈도수에 대한 정보는 count 리스트에 있으므로
index를 이용하여 빈도수를 참조한다.
이때 리스트의 원소의 빈도수가 더 크다면 stack[-1]의 오등큰수를 찾은 것이다.
따라서 스택의 상단에 있는 원소를 꺼낸다(pop).

만약 스택이 비어있거나 혹은
스택의 상단에 있는 원소의 빈도수가 더 크다면 어떤 일도 하지 않고 2️⃣로 넘어간다.

2️⃣ 리스트의 현재 원소를 스택에 삽입(append)한다.
(정확히 말하면 원소의 index를 삽입)

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))

count = [0] * 1000001 # 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)
for i in lst:
    count[i] += 1

stack = []
result = [-1] * N
for i in range(N):
	# 1️⃣
    while stack and count[lst[i]] > count[lst[stack[-1]]]:
        result[stack.pop()] = lst[i]
    # 2️⃣
    stack.append(i)

print(*result)

잘못된 정보, 오탈자를 발견하면 편하게 댓글로 말씀해주세요!
질문 또한 환영합니다 🤗