https://www.acmicpc.net/problem/18870
실패 이유 : 시간초과
N = int(input())
numbers = list(map(int, input().split()))
numbers_set = sorted(list(set(numbers)))
dic = {numbers_set[idx]: idx for idx in range(len(numbers_set))}
# dictionary 자료형 사용하여 O(1) 시간 복잡도
for i in numbers:
print(dic[i], end=" ")
- 이중 for문을 사용해 문제를 풀이하면 시간초과 발생
- 입력 숫자들로 집합을 만들어 중복을 제거하고 오름차순 정렬
- dictionary 자료형에 정렬된 숫자 집합값을 key로, 숫자 집합값의 인덱스를 value로 저장
- 입력 숫자 리스트를 돌면서 dictionary key 값에 해당하는 value를 출력
- 이전 풀이 O(n^2) 에서 O(n)으로 풀이 간결화
