백준<2751 수정렬하기2 > 와 <10989 수정렬하기3> 비교 (이선생이알려줌)

두 문제 시간제한과 메모리제한

두 문제는 정렬문제로 같은 문제이다. 수 정렬하기3의 N이 더 크고 수들의 값은 작은데 메모리 제한이 더 심해졌다.

---

수 정렬하기2 코드

import sys

n=int(input())
arr=[]
for i in range(n):
    arr.append(int(sys.stdin.readline().rstrip()))

arr.sort()
result=""
for i in range(n):
    result += str(arr[i])+" "

print(result)

기존의 sort함수를 사용한 것은 똑같다.

하지만, 처음 정수만 input으로 받는 것을 제외하고는 sys라이브러리의 readline메소드를 사용했다.

input("수를 입력하세요")처럼 input 메소드는 문자열을 인자로받고 입력받기 전 출력하는 과정이 있다. 이러한 과정은 입력받는 수들이 늘어날수록 시간이 시간이 오래 걸릴 것이다.

이 때, 시간제한인 1초를 넘어버린다.

따라서, int(sys.stdin.readline()로 대체한다. 

 

* 아무리 좋은 알고리즘이라도 입출력방법으로 인해 시간초과가 발생한다.

 

---

수 정렬하기3 코드

import sys

n=int(input())
cnt=[0]*10001

for i in range(n):
    t=int(sys.stdin.readline())
    cnt[t]+=1

for i in range(1,len(cnt)):
    if cnt[i]!=0:
        for j in range(cnt[i]):
            print(i,end=" ")

메모리 제한이 굉장히 엄격한 문제라 일반적인 sort로는 해결이 안된다.

카운팅소트를 이용해야한다. 대략적인 시간복잡도를 계산해보면 이러하다.

	1. 파이썬 내장 sort메소드	2. 카운팅 정렬
입력 시	N	N
정렬 시	NlogN	N
출력 시	N	10000

3N + logN >> 2N+10000

 

카운팅정렬의 특징은 입력받은 수가 배열의 인덱스로 작용한다. 입력받은 수가 몇 번 나오는지 입력받을 때 cnt라는 배열에 기록한다.

따라서 최대 10000까지 받을 수 있으므로 10000으로 고정이다.

cnt에 저장된 배열의 수만큼 그 인덱스를 출력해주면 되는 간단한 알고리즘이다.

하지만, 카운팅알고리즘이 딱 맞는 상황은 굉장히 제한적이다.

1. 입력 원소 중 음수가 있으면 안된다. 인덱스가 음수가 될 수 없으므로

2. 원소의 크기가 너무 크면 메모리에 과부하가 발생할 수 있다. 입력값이 곧 배열의 인덱스값이므로

만약 원소값이 100,000인 경우, 해당 크기의 배열이 필요하기 때문.