[Python/파이썬] 백준 알고리즘 18870번 - 좌표 압축

 

 

 

<풀이 1 - 시간 초과>

N = int(input())

coList = list(map(int, input().split()))
# 중복 값 제거한 후 정렬
coList_sort = sorted(list(set(coList)))

for coordinate in coList:
    print(coList_sort.index(coordinate), end=' ')

처음에 이렇게 풀었으나 시간 초과가 났다. 리스트.index(i)의 시간 복잡도는 O(N)이다.

인덱싱을 방법 중 더 낮은 시간 복잡도의 방법은 딕셔너리를 이용하는 방법이다. (O(1))

 

 

<풀이 2 - 성공>

N = int(input())

coList = list(map(int, input().split()))
# 중복 값 제거한 후 정렬
coList_sort = sorted(list(set(coList)))

# 시간 단축을 위해 딕셔너리 인덱싱을 사용
dic = {coList_sort[i]: i for i in range(len(coList_sort))}

for co in coList:
    print(dic[co], end=' ')

딕셔너리를 새로 만들어 거기에 coList의 원소를 key로, coList_sort의 인덱스를 value로 저장한다.

coList_sort는 coList에서 중복 값을 제거하고 오름차순 정렬한 리스트이다.

때문에 coList_sort에서 각 값의 인덱스는 문제에서 말하는 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같다.

(ex. coList_sort = [1, 2, 4] 라고 할 때 4의 인덱스는 2이다. 이 때, 4보다 작은 element는 두 개이므로 인덱스와 동일하다.)

그리고 출력할 때, coList에서 각 원소를 순서대로 꺼내서 그걸 key값으로 사용해 dic에 인덱싱해서 값을 구해내면 된다.

 

 

 

<핵심 정리>

1. list.index(i) 형태의 시간 복잡도 = O(N)

   index[i] 형태의 시간 복잡도 = O(1)

2. 리스트에서 어떤 원소에 대해서 그 원소보다 작은 원소들의 개수를 구하고 싶다면 오름차순 정렬시켜서 인덱스를 구하면 된다. (필요에 따라 list(set())으로 중복을 제거해줄 수 있다.)