문제
카운팅 정렬로 숫자 정렬하는 문제. 그러나 이 문제에는 함정카드가 하나 있다. (대충 함정좌 짤)
메모리 제한이 8MB밖에 안된다. 자바랑 코틀린만 많이 준다.
Reference
https://8iggy.tistory.com/123 (카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘)
https://seongonion.tistory.com/130 (계수(카운팅) 정렬 (Counting sort) with 파이썬(Python))
https://www.acmicpc.net/board/view/26132 (★☆★☆★ [필독] 수 정렬하기 3 FAQ ★☆★☆★)
https://scarlett-choi.tistory.com/9 ([백준 #10989] 수 정렬하기3(카운팅 정렬) – 파이썬(python))
풀이
문제를 보면 아시겠지만 이전의 정렬 문제와 달리 숫자가 중복이 된다. 우리야 숫자 같으니까 똑같이 두지 뭐 하지만 컴퓨터는 이게 뭐여 하면서 밥상뒤집기를 시전할 수도 있다. 그래서 이럴 때 필요한 게 카운팅 정렬임… 함정 얘기는 이따가 해드릴게여.
a = [1, 2, 6, 5, 6, 6, 4, 3, 3, 4, 2]
def count_sort(arr):
m = max(arr)
# 최댓값 도출
C = [0] * (m + 1)
# Counting Array 생성
for a in arr:
C[a] += 1
print("Counting Array: {}".format(C))
# counting Array에 채워넣는다
for i in range(1, m + 1):
C[i] += C[i - 1]
print("Array's Sum: {}".format(C))
# 누적합으로 바꾼다
result = [0] * len(arr)
# 정렬을 위한 배열
for a in arr:
result[C[a] - 1] = a
C[a] -= 1
print("Sorting... :{}".format(result))
# 정렬 콜
return result
print(count_sort(a))이게 카운팅 정렬의 코드이다. 뭐야 최댓값이 왜 나와요 저 배열 뭔데요…
카운팅 정렬이 진행되는 과정에서는 배열이 두 개 필요하다. 첫번째가 Counting Array, 두번째는 결과를 만들기 위한 배열이다. Counting Array는 말 그대로 이 배열에 어떤 원소가 몇 개 있느냐를 표시하기 위한 배열로, 배열 전체를 돌면서 원소를 세고 있을때마다 카운트를 하나씩 올리는 방식이다. 이렇게 배열 내 원소를 전부 셌다면, 그 다음은 누적합(개수의 누적합)을 구해 배열화하게 된다. 근데 이것만 하면 정렬이 되나요? 된다.
누적합 배열을 통해 개수를 유추할 수 있으니, 어디에서 어디까지 어떤 원소가 들어가게 되는 지 알 수 있기 때문에 알아서 채우면 된다.
그럼 저거 내면 되나요?
메모리 초과: YOU JUST ACTIVATED MY TRAP CARD (브금은 셀프)
위에서 자바랑 코틀린 말고 메모리가 8메가라고 했는데, 저거 일일이 받아서 배열에 저장하면 초과 뜬다.
import sys
N = int(sys.stdin.readline())
array = [0] * 10001
for i in range(N):
input_num = int(sys.stdin.readline())
array[input_num] = array[input_num] + 1
for i in range(10001):
if array[i] != 0:
for j in range(array[i]):
print(i)그래서 이거 내야됨. 아닛 이 짤막한 코드로 된다고? ㅇㅇ 됨 내가 봤음.
위에서 카운팅 정렬은 입력받은 배열에서 세기 위한 배열과 결과를 저장할 배열 두 개를 만든다고 했는데, 요 작고 소듕한 코드는 그 만드는 과정을 생략해버렸다.
그래서 만드는 배열은 0이 10001개인 배열 하나뿐이고, 숫자가 입력될때마다 배열의 입력받은 값에 해당하는 인덱스의 숫자를 하나 추가한다. 이게 뭔 소리냐면 배열이 다 0이고 입력값이 7이면 배열[7]을 0에서 1로 바꾼다는 얘기. 그리고 배열을 싹 돌아서 안에 0이 아닌 숫자가 있으면 그만큼 해당 숫자를 출력한다.
Reply