[★python_파이썬]백준_10989번_수 정렬하기3_풀이

공부하는허딩크 : https://www.youtube.com/live/MRweSf80fmw?feature=shared

 

기존 문제와 차이점은 시간제한과 메모리 제한이 있다.

 

뭐 별거 있겠어? 라는 마음으로 기존 코드를 가져다 쓴다.

<첫번째 시도 : 메모리 초과>

import sys

input = sys.stdin.readline

N = int(input())

A = [int(input()) for _ in range(N)]

A.sort()

for i in A:

    print(i)

 

흠.... 뭐가 문제일까? 문제 소개에는 카운팅 정렬을 쓰라고 나오는데 그게 뭔지 모른다.

30분동안 고민했는데 답이 안나온다. 구글링으로 바로 전환. => 계수 정렬을 사용하라고 하는데 그게 뭔지....

즉,  append나 sort를 사용하면 크기가 한정되어 있을때 사용을 못한다는 소리인건 알겠다. 실패가 뜨니....

 

첫번째 시도 이후 정렬알고리즘에 대해서 따로 학습을 했다. : https://heodinkcodingdiary.tistory.com/31

[python_파이썬] 정렬의 종류 (선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 힙정렬, 기수정렬, 계수정렬)

 

<두번째 시도 : 메모리 초과_정렬 알고리즘을 몇시간 고생하면서 학습하고 다시 왔는데 실패.>

N = int(input())

numbers = []

for _ in range(N):

    numbers.append(int(input()))

max_num = max(numbers)

m = max_num + 1

count = [0] * m

for i in numbers:

    count[i] += 1

index = 0

for i in range(m):

    for _ in range(count[i]):

        numbers[index] = i

        index += 1

for i in numbers:

    print(i)

 

평균시간 복잡도가 가장 낮은 계수정렬을 활용했는데 메모리 초과가 나왔다.

append때문인가??? 당황스럽다....

 

<세번째 시도 : 메모리 초과>

import sys

input = sys.stdin.readline

N = int(input())

count = [0] * 10001

numbers = [0] * N

for _ in range(N):

    count[int(input())] += 1

index = 0

for i in range(10001):

    for _ in range(count[i]):

        numbers[index] = i

        index += 1

for i in numbers:

    print(i)

 

이것도 메모리 초과가 뜨네? 뭐지 ;;;;

 

<네번째 시도 : 메모리 초과 _ 출력 for문을 제거하고 바로 출력>

import sys

input = sys.stdin.readline

N = int(input())

count = [0] * 10001

numbers = [0] * N

for _ in range(N):

    count[int(input())] += 1

index = 0

for i in range(10001):

    for _ in range(count[i]):

        numbers[index] = i

        print(numbers[index])

        index += 1

 

<다섯번째 시도 : .. %가 올라간다......맞았습니다.>

import sys

input = sys.stdin.readline

N = int(input())

count = [0] * 10001

for _ in range(N):

    count[int(input())] += 1

index = 0

for i in range(10001):

    for _ in range(count[i]):

        if count[i] > 0:

            print(i)

 

와....... 고민 많이 했다. 기존 numbers를 버리고 count로만 활용해서 바로 출력하니 통과가 되네....

아직도 기존 코드랑 차이는 잘 모르겠다.