728x90
반응형
문제 출처:https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
풀이:
sys import
n = int(input())
arr = list(map(int, input().split()))
arr_list = sorted(list(set(arr))) # 중복제거
arr_dic = {}
for i in range(len(arr_list)): # arr_list 에 길이만큼 포문을 돌려
arr_dic[arr_list[i]] = i # 딕셔너리를 만들어준다
for i in range(n): # 입력받은 n 만큼 포문을 돌려
arr[i] = arr_dic[arr[i]] # 딕셔너리에서 키에 arr[i]를 넣어 벨류를 찾아 arr를 만들어줌
print(*arr)
# * 는 언팩킹 [] 까줌
# for i in range(n):
# print(arr[i], end = ' ') print(*arr) 대신 가능한 카테고리의 마지막 문제답게 좀 어려웠다.
이 문제는 좌표압축 즉 각 숫자들의 순위를 0부터 출력하면된다
예를들어 1,10,100,1000 이면 0,1,2,3 이렇게 압출할 수 있다.
딕셔너리를 사용한 이유는
일반적은 for 문을 돌려 index를 찾아 프린트 하는것은 빅오가 O(n) 이라 시간초과로 실패한다
딕셔너리의 빅오는 O(1) 이다.
이 문제를 통해 딕셔너리에 대해 한번 보고 갔으면 좋겠다.
반응형
댓글