[백준] 18870번: 좌표 압축 python

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

📌  문제 해설

"Xi>Xj를 만족하는 서로 다른 좌표의 개수와 같아야된다" 라는 뜻은 즉 Xi가 리스트 안에서의 크기 순서를 출력하면 된다는 말

(크기 순서는 0부터 시작.)

즉, 리스트안에서 자기보다 작은 숫자의 개수를 세는 것이므로, 자신이 리스트 안에서의 크기 순서를 출력하면 됨

 

📌  코드

실패 코드 (시간 초과)

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

arr2 = sorted(list(set(arr)))

for i in arr:
    print(arr2.index(i), end = ' ')

list.index(i) → 시간 복잡도 O(n)

 

성공 코드

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

arr2 = sorted(list(set(arr)))

dic = {arr2[i]: i for i in range(len(arr2))}

for i in arr:
  print(dic[i], end=' ')

index[i] → 시간 복잡도 O(1)

 

✔️ 자세히 알아보자) arr2, dic도 print 해서 확인해보기

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

arr2 = sorted(list(set(arr)))
print(arr2)

dic = {arr2[i]: i for i in range(len(arr2))}
print(dic)

for i in arr:
  print(dic[i], end=' ')

결과

 

📍 결론

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

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

 

📌 파이썬 딕셔너리에 관해서..

1. 딕셔너리이름 = {"key값" : "value값"}
2. key 중복 허용 X
3. key가 중복 될 경우 마지막에 입력된 key의 value를 출력.

 

1번 예제)

dic = {"key1":"value1", "key2":"value2", "key3":"value3", "key4":"value4",}

print(dic["key1"]

#결과
# value1

 

2번 예제)

arr = [1, 0, 2, -4, 6, 33, 22]

dic = {arr[i]:i for i in range (len(arr))}

print("dic =",dic)
print("dic[33] = ",dic[33])

# 출력결과
# dic = {1: 0, 0: 1, 2: 2, -4: 3, 6: 4, 33: 5, 22: 6}
# dic[33] =  5

참고한 블로그 :

https://eunhee-programming.tistory.com/116

[코드짜는 문과녀:티스토리]