[알고리즘][파이썬] 백준_10989_수 정렬하기 3

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

10989번: 수 정렬하기 3

수 정열하기 1~2는 몸 풀기이고,

이 문제가 찐이다!

수 정열하기 1~2와 요구는 동일 한데,

메모리 제한에 주의해야 한다.

2750번 128MB, 2751번 256MB인데 반해

10989번은 8MB이다.

---

메모리 초과 "힙정렬, 퀵정렬"

# 힙정렬 시도(결과: 메모리 초과)
# 소스코드 출처(https://it-garden.tistory.com/128)
def heap_sort(a):
    for i in range(1,len(a)): # 최대 힙 만들기
        c = i
        while c != 0:
            r = (c-1) // 2
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            c = r

    for j in range(len(a)-1,-1,-1): # 힙 만들기
        a[0], a[j] = a[j], a[0]
        r = 0
        c = 1

        while c < j:
            c= 2 * r + 1
            if c < j -1 and a[c] < a[c+1]:
                c += 1
                
            if c < j and a[r] < a[c]:
                a[r], a[c]=a[c], a[r]
            r = c 

N = int(input())

lst = []
for i in range(N):
    lst.append(int(input()))
    
heap_sort(lst)

print(lst)

# 퀵정렬 시도(결과: 메모리 초과)
# 소스코드 출처(https://freedeveloper.tistory.com/377)
def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복 
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

N = int(input())
lst = []
for i in range(N):
    lst.append(int(input()))
    
quick_sort(lst, 0, len(lst) - 1)
print(lst)

 

시간, 공간 복잡도에서 유리하다고 하여

힙정렬, 퀵정렬을 시도해 보았다.

코드는 구글링하여 가져왔다.

하지만 이 문제에서는 통하지 않았다.

결과는 "메모리 초과"

---

시간 초과

# input이용 입력(결과: 시간 초과)
lst = [0]*10001

N = int(input())
for _ in range(N):
    num = int(input())
    lst[num] += 1

for i in range(len(lst)):
    if lst[i] >= 1:
        for _ in range(lst[i]):
            print(i)

 

위 코드로 "메모리 초과" 문제는 해결하였다.

하지만 "시간 초과"되어 코드의 수정이 필요했다.

시간 초과의 경우에는 값을 입력 받을때 "input()" 대신 "sys.stdin.readline()"를 사용하여 해결 할 수 있었다.

---

최종 제출코드

# 값 입력 sys.stdin.readline() 이용(결과: 맞았습니다!)
import sys

# 메모리를 8MB만 사용해야 하기 때문에 조건에 따라 10,000보다 작은 자연수의 lst 리스트를 미리 생성
lst = [0]*10001

N = int(input())
# 10,001개의 0이 들어 있는 lst 리스트에 값이 입력되는 주소에 1을 더함
for _ in range(N):
    num = int(sys.stdin.readline()) # 값 입력 sys.stdin.readline() 이용
    lst[num] += 1

# lst 리스트에서 어떤 주소의 값이 1 이상인 경우 해당 값 만큼 주소값을 반복해 출력함
for i in range(len(lst)):
    if lst[i] >= 1:
        for _ in range(lst[i]):
            print(i)