[백준/실버2/파이썬] 18870번 해결방법 (ps. 시간초과)

[백준/실버2/파이썬] 18870번 (ps.. 시간초과)

[문제 링크]

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

[나의 풀이]

#나의 풀이
import sys

n=int(sys.stdin.readline().rstrip())
xi=list(map(int,sys.stdin.readline().rstrip().split()))
xi_prime=sorted(xi)

for i in xi:
    print(xi_prime.index(i),end=" ")

입력을 sys.stdin.readline().rstrip() 으로 접근하였는데도 시간초과가 났다.

찾아보니 리스트.index(i) 의 시간복잡도가 O(N) 이다.

[새로 알게된 것, 다른사람 풀이]

# 다른 사람 코드
import sys 
N = int(sys.stdin.readline()) 
arr = list(map(int,sys.stdin.readline().split())) 
arr2 = [] 
arr2 = list(sorted(set(arr))) 

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

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

출처: https://eunhee-programming.tistory.com/116 [코드짜는 문과녀]

- 리스트.index(i) 의 시간복잡도가 O(N) 이다.

- arr2 = list(sorted(set(arr)))  -> set(arr) 집합형으로 중복을 제거 하고, 정렬해서 리스트로 반환한다.

- end=' ' 

- 딕셔너리의 시간복잡도는 O(1)

[최종 코드]

import sys

n=int(sys.stdin.readline().rstrip())
xi1=list(map(int,sys.stdin.readline().rstrip().split()))

xi=list(sorted(set(xi1)))
dic=dict()
for i in range(len(xi)):
  dic[xi[i]]=i

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