[정렬 알고리즘][파이썬][백준 10989] 정렬 알고리즘 기초 문제 팁

정렬 알고리즘 기초 문제들을 풀면서 어느정도 문제를 푸는 방식에 대한 감을 잡았다.

 

정렬 문제 풀이의 일관성을 위해서 내가 문제 푸는 방식을 정리해보려한다.

 

먼저 파이썬에서는 기본적으로 정렬을 하는 함수를 제공한다.

 

바로 sort와 sorted 이다.

 

sort와 sorted

 

li= [1, 3, 6, 2, 3, 4] 이러한 리스트가 있다고 하자.

 

li를 원본 리스트라고 하고 이 원본 리스트 자체를 정렬하고 싶다면 li.sort()를 사용한다.

 

정렬 후 print(li)로 원본 리스트를 출력해보면 

 

출력

[1, 2, 3, 3, 4, 6]

 

제대로 출력되는 모습을 볼 수 있다.

 

sorted의 경우 원본 리스트를 정렬하는 것이 아닌 정렬된 새로운 리스트를 반환하는 함수이다.

 

li2 = sorted(li) 와 같이 사용하고 li와 li2를 출력해보면

 

li 출력

[1, 3, 6, 2, 3, 4]

 

li2 출력

[1, 2, 3, 3, 4, 6]

 

원본 리스트가 변경되지 않은 모습을 확인할 수 있다.

 

정렬 문제 풀이법

기초 정렬 문제에서는 크게 풀이가 두 가지로 나뉜다.

 

첫 번째로 그냥 sort 함수를 사용한 정렬과 두 번째로 리스트의 인덱스를 사용한 방법이 있다.

 

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

2750번: 수 정렬하기

위 문제의 경우 그냥 sort 함수로 정렬을 한 뒤 출력을 하면 되는 문제이다.

 

입력받는 개수가 크지 않다면 웬만해선 sort 함수로 문제를 해결할 수 있다.

 

sort 함수에는 정렬 기준을 정할 수도 있는데 아래 포스팅을 참고하면 좋을 듯 하다.

 

https://growth-coder.tistory.com/72

 

그런데 만약 입력받는 개수가 매우 크다면 시간 초과가 발생할 수 있다.

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

10989번: 수 정렬하기 3

 

위 문제는 입력받는 값의 개수가 최대 10,000,000까지 받을 수 있다.

 

이렇게 리스트의 길이가 매우 클 경우 sort 함수로는 시간 내에 문제를 해결할 수 없다.

 

이럴 경우 리스트의 인덱스를 활용하면 된다.

 

sort 함수를 사용하게 되면 리스트의 값을 기준으로 정렬을 하게 된다.

 

이제 리스트의 값이 아니라 리스트의 인덱스를 활용할 차례이다.

 

일단 모든 값이 0인 이름이 li인 리스트를 생성한다.

 

li=[0]*101

 

그리고 1, 5, 3, 6, 2, 1 순서대로 값을 입력받는다고 하자.

 

그러면 li[1]의 값을 증가시키고 li[5]의 값을 증가시키고

 

이렇게 입력받은 값을 인덱스로 활용하는 것이다.

 

그러면 li의 모습은 다음과 같을 것이다.

 

인덱스	0	1	2	3	4	5	6	7	...
값	0	2	1	1	0	1	1	0	...

출력을 한다고 하면

 

인덱스 1부터 끝까지 증가시키면서 값이 아닌 인덱스를 출력하는 것이다.

 

리스트의 값은 해당 인덱스를 출력할 횟수가 된다.

 

이 방식의 장점은 입력받을 때부터 그냥 정렬을 하는 것이나 마찬가지이므로 sort 함수를 사용하는 것보다 시간을 많이 단축시킬 수 있다.

 

이 방식으로 10989 문제를 풀어보자.

 

입력받는 수가 10,000보다 작거나 같은 자연수이므로 길이가 10,001이고 값이 모두 0인 리스트를 생성한다.

 

길이가 입력받는 수의 최대값보다 1이 큰 이유는 리스트의 인덱스는 0부터 시작하기 때문이다.

 

물론 길이가 10,000인 리스트를 만들어도 되지만 헷갈릴 수 있기 때문에 그냥 길이가 10,001인 리스트를 만드는 게 좋다.

 

 

<전체 코드>

import sys
n=int(input())
num=[0]*10001
for _ in range(n):
    num[int(sys.stdin.readline())]+=1
for i in range(1, 10001):
    while num[i]>0:
        print(i)
        num[i]-=1

 

그러나 이 방식에도 단점이 존재한다.

 

바로 리스트의 길이가 입력받는 값의 최댓값에 의존한다는 점이다.

 

1. 메모리 초과

 

입력받는 값의 최댓값이 매우 크다면 그만큼의 길이를 가진 리스트를 만들어야 하고 메모리 초과가 발생할 위험이 존재한다.

 

또한 1과 10,000,000을 가진 리스트를 정렬한다고 하면 9,999,999개가 낭비되기 때문에 메모리 낭비도 심하다.

 

2. 음수 불가능

 

인덱스는 0부터 시작하기 때문에 음수를 입력받을 수가 없다.

 

두 방식 모두 장단점이 존재하기 때문에 문제 유형에 따라 적절한 방법을 선택하면 좋을 듯 하다.