단계별 풀기 정렬에 백준 18870번 좌표압축 문제
리스트의 중복을 시간복잡도까지 생각하며 풀어야할 문제였고 이 기술은 다른데에서도 쓰일 것 같으니 그때 되면 또 다시 리스트 중복제거 방법을 검색 할 것 같아서 글을 써야 되겠다 라고 생각하였다.
시간초과 틀린코드
n = int(input())
arr1 = list(map(int,input().split()))
arr2 = list(sorted(set(arr1))) # 중복 값 제거한 후 정렬
#아래 2중 for 문은 arr1의 길이의 제곱배로 도는 O(n^2)의 시간복잡도를 가진다.
#굉장히 비효율적이다.
for i in range(len(arr1)):
for j in range(len(arr2)):
if arr2[j] == arr1[i]: # 값이 일치하면
arr1[i] = j # 인덱스 값이 해당 값으로 바뀜
for i in range(len(arr1)):
print(arr1[i],end=' ')
Python
복사
위 코드는 최악의 경우 arr1의 길이만큼의 제곱배로 연산을 수행할 것이다. 그렇기 떄문에 시간 오류가 난다.
맞는코드
n = int(input())
arr1 = list(map(int,input().split()))
arr2 = list(sorted(set(arr1))) # 중복 값 제거한 후 정렬
# 딕셔너리 문법 : x = {'a': 10, 'b': 20, 'c': 30, 'd': 40}
# 딕셔너리를 만드는데 arr2[i] 가 키 값이고 벨류는 arr2의 인덱스 값이다.
dic = {arr2[i] : i for i in range(len(arr2))}
for i in range(len(arr1)):
print(dic[arr1[i]],end=' ')
Python
복사
위 처럼 코드를 바꾸면 print를 수행하기 위해 원하는 값을 찾는 과정에서 딕셔너리에 바로 key값을 줌으로써 O(1)의 시간복잡도만 수행하고 배열 길이만큼 돌기 위해서 arr1의 길이만큼 O(n)만큼만 돈다.
위에서 O(n^2) 이었던 시간복잡도를 확 줄일수 있다.