[백준 18870 Python] 좌표 압축 - ItisFuture

 

내가 쓴 정답 코드

n = int(input())
n_list = list(map(int,input().split()))
n_dic = {i:0 for i in n_list}
n_sorted_list = sorted(n_list)
cnt = 0
prev = n_sorted_list[0]
for i in n_sorted_list:
    if i == prev:
        n_dic[i] = cnt
    else:
        cnt+=1
        n_dic[i] = cnt
    prev = i
    
for idx,i in enumerate(n_list):
    n_list[idx] = n_dic[i]
print(*n_list)

풀이 아이디어

1. 제일 작은 숫자가 0 임을 파악

2. 오름차순으로 +1씩

    2-1. 주어진 값에 대하는 순서를 딕셔너리에 업데이트

3. 숫자 리스트에 각 숫자를 순서로 대체

 

여담

이 풀이와 대부분의 풀이에서 1초 내외의 시간이 경과됐다.

예전에 검색을 해봤지만 정확히 기억이 안 나서 파이썬은 1초에 몇 번을 계산하는지 궁금해져서 검색해보니 

2천만 번이라 하여 내 코드에서 어느 정도의 계산을 했나 궁금했다.

sorted()는 병합 정렬을 기반으로 만들어졌고 시간 복잡도는 O(NlogN)이다.

N번 반복하는 코드들은 4번 쓰여졌다.

문제에서 최대 백만 개의 데이터가 올 수 있다는 점을 생각하면

내 코드에서 최대 연산 횟수는 약 천만번이다.

따라서 1초라는 결과에 납득을 했다.

sorted()함수에 key값 활용하여 유용하게 써먹어야겠다.

https://devmath.tistory.com/23

[파이썬 Python] 정렬 라이브러리 / sorted() , sort() , key 값