좌표압축

❓문제
https://www.acmicpc.net/problem/18870

❗문제 정리
사용한 기능:
시간 초과 해결을 위한 sys.stdin.readline
딕녀서리

📑코드

import sys
input=sys.stdin.readline

n=int(input())
numbers=list(map(int, input().split()))

sorted_numbers=sorted(set(numbers))
values=[x for x in range(len(sorted_numbers))]
dict_num=dict(zip(sorted_numbers,values))
for i in numbers:
    print(dict_num[i],end=' ')

📝코드 설명

sorted_numbers=sorted(set(numbers))

1. 임시 배열에 중복이 없고 정렬된 상태를 만들어 놓는다.

values=[x for x in range(len(sorted_numbers))]
dict_num=dict(zip(sorted_numbers,values))

2. 임시 배열의 크기만큼 0부터 오름차순으로 값이 채워진 리스트를 만들어 딕셔너리의 값으로 사용한다. 예시) {-10:0, -9:1, 2:2, 4:3} 값:번째

• 딕셔너리를 사용해야 시간 초과 문제를 해결할 수 있다. 키에 해당하는 값(번째)를 바로 리턴해줄수 있기 때문이다. index()함수를 사용하면, 정렬되지 않은 모든 수에 대한 탐색을 해야하기 때문에 시간복잡도가 증가한다.

🎖제출 결과

💡insight