💡문제
크기가 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)을 공백으로 구분해 출력한다.
예제입력
7
1 1 2 3 4 2 1예제출력
-1 -1 1 2 2 1 -1📖내가 작성한 Code
import sys
class Node:
def __init__(self, num, data):
self.number = num
self.data = data
self.next = None
class FindNGF:
def __init__(self, size):
self.count_f_dict = {}
self.result = [-1] * size
self.top_node = None
def count_f(self, data):
if data in self.count_f_dict:
self.count_f_dict[data] += 1
else:
self.count_f_dict[data] = 1
def find_NGF(self, num, data):
new_node = Node(num, data)
while self.top_node and self.count_f_dict[self.top_node.data] < self.count_f_dict[data]:
self.result[self.top_node.number] = data
self.top_node = self.top_node.next
if self.top_node:
new_node.next = self.top_node
self.top_node = new_node
def main():
size_a = int(sys.stdin.readline())
list_a = list(map(int, sys.stdin.readline().split()))
new_FindNGF = FindNGF(size_a)
for number in list_a:
new_FindNGF.count_f(number)
for num, data in enumerate(list_a):
new_FindNGF.find_NGF(num, data)
return new_FindNGF.result
if __name__ == "__main__":
print(" ".join(map(str,main())))
✍️풀이과정
17298번 문제인 오큰수와 궤를 같이하는 문제라고 생각하여 접근해봄. 먼저 수열의 크기가 1,000,000이므로 이중 반복문은 안된다고 생각하여 접근.
각 원소의 빈도를 빠르게 조회하기 위하여 해시 자료구조를 사용. 그 이후에는 비교하면서 확인. list도 좋지만 계속해서 자료형 만들어 보기 위하여 Node 만들어봄.
🧠 코드 리뷰
-
collections.Counter 활용 : count_F 메서드는 간단하므로 상관 없지만, 한줄로 깔끔히 작성 가능
-
stack을 list로 간단히 구현 : 직접 만들어 쓰는 건 자료구조 구현 연습 측면에서는 좋지만, Python에서 append()/pop()은 효율적
-
입력/출력 로직 분리: main() 함수 내에서 입력을 받고, 결과만 출력하도록 구조를 분리하는 것을 추천. 재사용성을 높이기 위해 좋음.
🛠️AI 개선 코드
import sys
from collections import Counter
class NGFFinder:
"""오등큰수(NGF, Next Greater Frequency)를 찾는 클래스.
Attributes:
nums (list): 입력 수열
size (int): 수열의 길이
freq (Counter): 각 숫자의 등장 빈도
result (list): 오등큰수를 저장할 리스트
stack (list): 단조 스택(인덱스 저장)
"""
def __init__(self, nums):
self.nums = nums
self.size = len(nums)
# 1) 등장 빈도를 한 번에 계산 (collections.Counter 사용)
self.freq = Counter(nums)
# 2) 결과 배열 초기화
self.result = [-1] * self.size
# 3) 스택: 단조 스택 구조를 리스트로 구현
self.stack = []
def find_ngf(self):
"""단조 스택을 사용하여 오등큰수를 찾고, 결과 리스트를 반환한다."""
for i in range(self.size):
# 스택의 top에 있는 원소 빈도가 현재 원소 빈도보다 작으면 pop하여 갱신
while self.stack and self.freq[self.nums[self.stack[-1]]] < self.freq[self.nums[i]]:
top_index = self.stack.pop()
self.result[top_index] = self.nums[i]
# 현재 인덱스를 스택에 push
self.stack.append(i)
return self.result
def main():
input = sys.stdin.readline
n = int(input().strip())
nums = list(map(int, input().split()))
# NGFFinder 객체 생성 후 오등큰수 계산
ngf_finder = NGFFinder(nums)
answer = ngf_finder.find_ngf()
# 결과 출력
print(" ".join(map(str, answer)))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
