[CodeUp][Python]3004번 풀이

오늘은 3004번에 대해서 설명을 드리겠습니다. 데이터 정렬 문제는 많은 온라인 저지 사이트에서 단골로 나오는 문제이기도 하고 아마도 처음으로 여러분들께 메모리 초과, 시간 초과의 압박을 제공하는 문제일겁니다. 저도 처음 데이터 정렬 문제를 풀 때 시간 초과에 걸려서 상당히 고생을 했던 생각이 나는데요. 그래도 가급적이면 누군가의 코드를 찾아보기 보다는 어떻게 하면 데이터 정렬에 걸리는 시간을 단축할 수 있을까에 대한 고민을 꼭 해보셨으면 좋겠습니다. 그럼 풀이 시작해보겠습니다.

 

https://codeup.kr/problem.php?id=3004 

데이터 재정렬

아마 이런 식으로 대놓고 시간복잡도와 공간복잡도를 고민하도록 강요하는 문제가 아닌 경우, 대부분 sort()를 이용해서 데이터 정렬을 시켰던 경험이 있으실 겁니다. 잠깐 그런 코드를 볼까요?

sort를 이용한 데이터 정렬 코드

n = int(input())
num_list = list(map(int, input().split()))
sorted_num_list = sorted(num_list)
number_sequence = []
for i in range(n):
    for j in range(n):
        if sorted_num_list[j] == num_list[i]:
            number_sequence.append(j)
for i in range(n):
    print(number_sequence[i], end = ' ')
#O(n^2)

깔끔하니 보기 좋죠? 내용도 단순하게 sorted()로 정렬된 데이터를 만들고 그 인덱스를 이용해 원래 자료의 순서를 출력하는 코드입니다. 하지만 이렇게 풀었다간 이 문제는 풀 수 없습니다. 온라인 저지 사이트를 이용할 때 처음으로 신경 써야할 시간 제한에 대한 얘기와 함께 설명해보겠습니다.

 

다른 글에서 한 번 설명을 짧게 설명을 드린 적이 있는 시간복잡도에 대한 내용을 간단하게 짚고 넘어가겠습니다. 시간복잡도라는 개념이 있는데요. '시간복잡도' 는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다(위키백과). 시간복잡도는 주로 Big O 표기법을 사용하구요. 보통 O(n), O(log(n)), O(n^2) 등의 방법으로 표현합니다. 괄호안의 n으로 이뤄진 식은 가장 오래걸리는 연산을 나타내죠. 조금 설명이 길어졌는데 바로 위의 코드에 적용시켜보겠습니다.

 

위의 코드는 O(n^2)의 시간복잡도를 가집니다. 위의 입력이나 리스트의 선언은 넘어가고 가장 오래걸리는 연산인 반복문을 살펴볼까요?

for i in range(n):
    for j in range(n):
        if sorted_num_list[j] == num_list[i]:
            number_sequence.append(j)

i를 0부터 n-1까지, 그 안에서 다시 j를 0부터 n-1까지 반복하면서 sorted_num_list[j]와 num_list[i]를 비교하고 리스트에 원소를 추가하는 반복문인데요. 반복문의 진행을 (i,j)로 간략화해서 표현하면 (0,0), (0,1), (0,2), (0,3), ... (0,n-1), (1,0), (1,1), ... (1, n-1), (2, 0), ... (n-1, n-1) 뭐 이런식으로 되겠죠. 그렇다면 연산의 수는 n*n으로 n^2이니 시간복잡도는 O(n^2)이 되는겁니다. 아래에도 반복문이 하나 있지만 가장 오래 걸리는 연산을 기준으로 표기하기 때문에 무시합니다. 짧게 설명하려 했는데 좀 길어졌네요.

 

그렇다면 시간 제한과 위의 코드를 잠깐 비교해볼까요? 해당 문제에서의 제한 시간은 1 sec 입니다. 이것은 확실하진 않지만 제가 들은 얘기로는 연산 한 번에 1/10^8 sec 정도라고 생각하면 된다고 하더라고요. 해당 문제에서의 n의 범위는 1~50000 입니다. 최대 n이 주어졌다고 가정할 때 50000^2 = 2,500,000,000 이네요. 25억이죠? 25초라니, 시간 제한인 1초를 엄청나게 넘겨버렸죠. 이런식으로 본인 코드의 시간복잡도와 입력 데이터의 갯수, 제한 시간 등을 지표로 비교하면서 코드를 짜는 과정을 익혀두시면 두고 두고 도움이 될 겁니다. 물론 저도 아직 잘 못합니다만...

 

그러면 이제 당면 과제가 정해졌네요. O(n^2)의 시간복잡도를 O(n)이나 O(nlog(n))등으로 줄여야합니다(n = 50000 이라고 하면 각 50000, 234948 정도의 연산횟수를 가집니다. 1초 안에 충분히 들겠죠).

 

Counting Sort(계수 정렬)를 이용한 풀이

n = int(input())
cnt = [0 for i in range(500001)]
num_list = list(map(int, input().split()))
for i in range(n):
    num = num_list[i]
    cnt[num] += 1
for i in range(len(cnt)-1):
    cnt[i+1] += cnt[i]
for i in num_list:
    print(cnt[i]-1, end = ' ')
#O(n)

사실 다른 방법도 분명히 있을텐데 마침 제가 얼마 전에 counting sort를 활용해서 백준 문제를 푼 경험이 있어서 그 때 사용한 코드를 여기에 맞게 살짝 변형시켜봤습니다. 저도 상당히 counting sort를 이해하는데 도움이 되었던 사이트 링크를 남깁니다. https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

 

간단하게 설명을 하자면 미리 숫자의 최대값에 해당하는 리스트를 만들어 놓고 입력되는 숫자를 미리 만든 리스트의 인덱스로 사용을 하는 방식입니다. 가령 5개의 데이터가 들어오고 가장 큰 숫자가 10 이라고 한다면 cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 이라는 리스트를 만들고 1, 3, 5, 7, 9 라는 숫자들이 들어온다면 각 숫자를 cnt의 인덱스로 사용해 들어온 갯수만큼 해당 원소의 값을 늘려줍니다. 위와 같다면 cnt = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]이 되겠죠. 입력 숫자가 0,0,0,1,1 이라면 cnt = [3, 2, 0, 0, 0, ..., 0] 이렇게 될거구요. 이렇게 만든 다음 cnt[i+1]에 cnt[i]를 계속 더해줍니다. cnt = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]라면 cnt = [0,1,1,2,2,3,3,4,4,5] 가 됩니다. 그리고 cnt의 인덱스가 그대로 정렬된 숫자가 되므로 입력과 비교하면서 꺼내면 되는 방법인데 이 문제에서는 정렬된 숫자가 아닌 그 순서를 출력하는게 목적이죠? 따라서 반복문으로 꺼내주면 해결이 되는 문제입니다(단, 0~n-1로 출력해달라고 했으므로 1씩 빼줍니다).

 

잘 해결들 하셨나요? 사실 처음 이런 정렬 문제를 풀어보신 분들에게는 상당히 어려웠으리라 생각됩니다. 거기다 검색을 해보셔도 데이터 정렬 알고리즘은 워낙 많기 때문에 다들 푸는 방식이 많이 다르지 않았을까 예상하는데요. 제가 위에서 사용한 방식인 counting sort는 O(n)의 시간복잡도를 갖지만 입력 숫자의 범위가 크거나, 또는 입력이 음수로 주어질 때 사용하기 힘들다는 단점이 있습니다. 따라서 보통은 O(nlog n)의 시간복잡도를 갖는 Quick Sort를 일반적으로 사용한다고 하니, 저도 다음에 한 번 해당 내용에 대해 정리를 해보도록 하겠습니다. 오늘도 긴 글 읽어주셔서 감사합니다.

 

계수 정렬이 좀 더 궁금하시다면,

[Algorithm][Python] 계수 정렬(Counting Sort) 알고리즘 + 코드

[Algorithm][Python] 계수 정렬(Counting Sort) 알고리즘 + 코드