본문 바로가기

Coding Tests/백준 온라인

(Python) boj_10989

<문제>

 

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

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

이 문제는 메모리 제한이 정말 작기에,  N(1 ≤ N ≤ 10,000,000) 갯 수의 수를 모두 배열에 담아 정렬하기에는 무리가 있습니다. 또 N의 범위가 수는 10,000보다 작거나 같은 자연수 이므로, 해당 문제에서는 계수 정렬을 사용해 줍니다. 

 

 

< 정답 코드 >

 

import sys
N = int(input())

arr = [0]*10001

for _ in range(N):
    i = int(sys.stdin.readline())
    arr[i] +=1
    
for i in range(10001):
    if arr[i] != 0:
        for _ in range(arr[i]):
            print(i)

 

Python으로 제출 시 정답 판정을 받게 되지만, pypy로 제출하면 메모리 초과를 받게 됩니다. 그래서 pypy 제출 시에는 아래와 같이 sys.stdout.write() 함수를 사용해 줍니다. 

 

import sys
N = int(input())

arr = [0]*10001

for _ in range(N):
    i = int(sys.stdin.readline())
    arr[i] +=1
    
for i in range(10001):
    if arr[i] != 0:
        for _ in range(arr[i]):
            sys.stdout.write(str(i)+'\n')

 

sys.stdout.write() 함수는 줄 바꿈이 없이 출력되기에 '\n' 개행 문자를 삽입해 줄이 바뀌도록 해줍니다.