Search
Duplicate
🪔

파이썬 리스트 중복제거하기

간단소개
알고리즘공부
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
알고리즘
Python
태그
알고리즘
python
Scrap
8 more properties
단계별 풀기 정렬에 백준 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) 이었던 시간복잡도를 확 줄일수 있다.