[백준 18870번] 좌표 압축 - 파이썬(python)

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

풀이 설계

• set으로 리스트의 중복을 제거하고 정렬한다.
• 정렬된 리스트에서 해당 숫자의 인덱스를 찾아서 lst 값을 바꿔준다.

1차 시도 (시간초과)

n = int(input())
lst = list(map(int, input().split()))
sort_lst = sorted(set(lst))
for i in range(len(lst)):
    lst[i] = sort_lst.index(lst[i])
print(*lst)

2차 시도 (성공)

• 1차 시도에서 매번 리스트에서 index를 사용해서 찾는데 시간이 오래거리는 것같아서 딕셔너리로 숫자와 인덱스를 모두 저장해서 출력하는 방식으로 풀이했다.

n = int(input())
lst = list(map(int, input().split()))
sort_lst = sorted(set(lst))
index_dict = {sort_lst[i]: i for i in range(len(sort_lst))}
for num in lst:
    print(index_dict[num], end=' ')

후기

• 첫번째 방법으로 시도했을때 시간초과가 날 것 같기는 했다. 예전에 다른 문제에서 find를 사용해서 일일히 찾다가 시간초과가 났었어서... 어김없이 시간초과가 났다.
• 그래서 정렬한 리스트를 딕셔너리 형태로 인덱스를 저장하고 딕셔너리의 키로 밸류값을 찾는 방식을 사용했다.