[CodingTest] python 백준 Baekjoon #18870 좌표 압축 / 정렬 / index( ) 시간복잡도

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

18870번: 좌표 압축

 

문제는 쉬운데 시간 초과가 나서 검색해서 풀었다.

 

시도 1 - 시간초과

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
#결과값 저장 리스트
res = [0]*n

#집합으로 묶고 내림차순 정렬
set_arr = sorted(set(arr),reverse = True)

#집합으로 묶인 리스트의 인덱스 거꾸로 저장 
cnt_lst = [len(set_arr)-i-1 for i in range(len(set_arr))]

for i in range(len(arr)):
    if arr[i] in set_arr:
        res[i] = cnt_lst[set_arr.index(arr[i])]        
print(' '.join(map(str,res)))

 

set을 활용해 집합으로 바꾸어 중복값을 없애고 해당 숫자 보다 작은 숫자의 갯수를 cnt_lst에 저장했다.

그리고, arr과 set_arr을 비교하면서, 값이 같다면, 해당 숫자가 있는 set_arr의 인덱스를 cnt_lst에 넣어 res에 저장했다.

값은 잘 나오는데 시간초과라서 생각하다가 cnt_lst는 단순히 인덱스 저장 리스트라서 필요가 없을 것 같아서 아래에서 삭제해주었다.

 

 

시도 2 - 시간초과

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
#결과 저장 리스트
res = [0]*n
#arr을 집합화하고 내림차순 정렬
set_arr = sorted(set(arr))
for i in range(len(arr)):
    if arr[i] in set_arr:
        res[i] = set_arr.index(arr[i])

sys.stdout.write(' '.join(map(str,res)))

 cnt_lst 없애면서 내림차순하지 않고 오름차순으로 바꿔 코드를 더 깔끔하게 수정했지만 또다시 시간초과 .. ㅠ 

 

이유를 모르겠어서 검색했더니 나랑 풀이가 비슷한 사람이 있었다.

이유는 index() 때문이었다는 것!!!

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

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

그래서 딕셔너리를 활용했다고 한다.

dict는 시간복잡도 O(1)

 

시도 3 - 성공

import sys
from typing import List
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
#결과 저장 리스트
res = [0]*n
#arr을 집합화하고 내림차순 정렬
set_arr = sorted(set(arr))
dic = {set_arr[i]:i for i in range(len(set_arr))}
print(" ".join(map(str,[dic[item] for item in arr])))

 

 

다른 사람 코드도 비슷하다.

 

 

참고: https://gudwns1243.tistory.com/52