BOJ/백준-10989-python

문제📖

풀이🙏

• 첫째 줄에 수의 개수 N이 주어진다.
• 둘째 줄부터 N개의 줄에는 숫자가 주어진다.
• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
• 시간 제한 3초, 메모리 제한 8MB이다.
  -> 처음에 메모리 제한은 신경 못쓰고 시간 제한에만 포커스를 맞추어 quick sort로 구현을 해보았지만 메모리 제한으로 인해 실패했다.
  -> list문제에서 메모리 제한이 있다면 미리 틀을 만들어놓은 후 증감식으로 개수를 세는 것이 상당히 유리하다.

코드💻

수정 전 메모리 초과 코드

# boj, 10989 : 수 정렬하기3, python3
import sys

def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if( ARRAY_LENGTH <= 1):
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
        LESSER = [ element for element in ARRAY[1:] if element <= PIVOT ]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)

N = int(input())
nums = [int(input()) for i in range(N)]

print(("\n").join(map(str, quick_sort(nums))))

수정 후 성공 코드

import sys

N = int(sys.stdin.readline())
nums = []
result = [0 for _ in range(10001)]

for i in range(N):
    num = int(sys.stdin.readline())
    result[num] += 1
    
for i in range(len(result)):
    for j in range(result[i]):
        print(i)

결과😎

출처📝

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

github

github