백준 10989번 풀이

문제

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

10989번: 수 정렬하기 3

카운팅 정렬로 숫자 정렬하는 문제. 그러나 이 문제에는 함정카드가 하나 있다. (대충 함정좌 짤)

메모리 제한이 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이 아닌 숫자가 있으면 그만큼 해당 숫자를 출력한다.