교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 6 정렬
실전문제 6-4 계수 정렬 171p
계수 정렬 기본예제
문제
별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
제시된 데이터 : 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2
노트
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 생성하고(max-min+1), 모든 데이터를 0으로 초기화 한다.그리고 제시된 데이터의 값과 동일할 때 1씩 리스트에서 증가해준다.
풀이
arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
board = [0]*(max(arr)+1) #0부터 최댓값까지 board에 넣기
for i in range(len(arr)):
board[arr[i]]+=1
for i in range(len(board)):
for j in range(board[i]): # 더해진 횟수만큼 현재 인덱스 출력
print(i,end=" ")계수 정렬
- 시간 복잡도 : O(N+K), K는 데이터의 최댓값
- 공간 복잡도 : O(N+K) , 최대가 백만을 넘지 않으면 효율적
데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용(모든 범위를 담을 수 있는 크기의 리스트를 선언해야하기 때문)
References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저
