메모리 제한이 많음 -> 순서를 따로 저장(Hash)해두지 않으면 시간 초과 발생할 것이라고 유추 가능
순서만 비교할 것이기 때문에 num_list를 sort하기 전에 set으로 중복 값을 없앴다면 더 간단하게 해결 가능
import sys
n = int(input())
num_list = sys.stdin.readline().rstrip().split()
num_list = list(map(int, num_list))
rank = 0
mean_num = min(num_list)
num_rank = {}
for i in sorted(num_list):
if i > mean_num:
mean_num = i
rank += 1
num_rank[i] = rank
print(*[num_rank[i] for i in num_list])
다른 사람 풀이
시간 초과 발생 풀이
$O(n)$으로 index를 접근하는 과정에서 시간 초과 발생
sort로 중복 값을 없애 index가 곧 순서가 됨
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr2 = sorted(list(set(arr)))
for i in arr:
print(arr2.index(i), end = ' ')
성공 풀이
dict을 구성해 $O(1)$의 시간 복잡도로 문제 해결
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
print(dic[i], end = ' ')