[백준] 18870 좌표 압축 - 파이썬

18870번: 좌표 압축

---

시간 초과

import sys
n = int(input())
lst = list(map(int, sys.stdin.readline().split()))

tmp = set(lst)

result = [0] * n
for i in range(n):
  for t in tmp:
    if t < lst[i]:
      result[i] += 1
  print(result[i], end=" ")

여기서는 어차피 한 줄로 받으니까 sys.stdin.readline()으로 받을 필요는 없는 건가?

 

예제를 보니까 자기보다 작은 수의 숫자를 세면 되는 것 같은데 거기서 이제 똑같은 수는 한 번만 세는 것 같아서 일단 set을 이용해서 중복되는 수를 없앴다.

 

그리고 그냥 무식하게 리스트랑 중복되는 수를 없앤 tmp랑 비교해가면서 자기보다 작은 숫자 세고 그 값을 리스트에 담아서 출력했는데 역시나 시간 초과가 발생했다. 

 

이 문제는 그냥 다른 사람들 풀이를 참고했는데 인덱스를 이용하는 방법이 있었다.

그니까 중복을 없앤 리스트를 정렬하면 인덱스 자체가 크기 순서가 되는 것이다. 

 

예제가 아래와 같을 때

2 4 -10 4 -9

중복을 없애고 정렬하면

-10 -9 2 4

인데 이 친구들의 인덱스 자체가 바로 크기 순서다.

 

이 풀이법을 적용해서 짠 코드는 이런데 이것도 시간 초과가 발생한다.

import sys
n = int(input())
lst = list(map(int, sys.stdin.readline().split()))

tmp = sorted(list(set(lst)))

for n in lst:
  print(tmp.index(n), end = " ")

왜냐면 list.index(i) 형태의 시간 복잡도가 O(N)이기 때문에 매번 최대 1,000,000번의 수행이 이루어지게 돼서

시간 초과가 뜨는 것이다.

 

시간 초과를 피하기 위해 딕셔너리를 사용하면 다음과 같다.

import sys
n = int(input())
lst = list(map(int, sys.stdin.readline().split()))

tmp = sorted(list(set(lst)))
dic = {tmp[i] : i for i in range(len(tmp))}

for n in lst:
  print(dic[n], end = " ")

여기서 dic[n]의 시간 복잡도는 O(1)이다.