[python/백준] 10989: 수 정렬하기 3

1306 단어 algorithmalgorithm

문제

풀이

이 문제는 메모리 제한이 너무 적어서 sort를 사용할 수 없다.
게다가 for문에서 숫자를 입력 받기 위해 input을 사용해도 메모리 초과로 문제를 통과할 수 없다.

따라서 sort를 쓰지 않고, intput 대신 int(sys.stdin.readline()) 이 함수를 쓰는것이 이 문제의 핵심이다.

문제에서 N개의 줄에 수가 주어지는데, 이 수는 10000보다 작거나 같은 자연수라고 한다. 그렇다면 10001 길이(0번째 배열 포함)의 배열을 선언해서 만약 숫자 1이 두개라면 배열[1] = 2로 지정해서, 숫자 1을 두 번 print하는게 더 효율적인 방법일 것이다.

코드를 보면 더 이해가 쉬울 것이다.

코드

import sys

N  = int(sys.stdin.readline())
arr = [0]*10001

for _ in range(N):
    num = int(sys.stdin.readline())
    arr[num] += 1 # arr[num]에 num이 들어온 개수 count 

for i in range(10001): 
	# arr[i]에 숫자가 들어왔다면 
    if arr[i] != 0:
    	# arr[num]에 num이 들어온 개수 만큼 출력 
        for j in range(arr[i]): 
            print(i)

✨ 후기


sort에서 pypy3가 python3보다 성능이 앞선다 생각했는데,
메모리 사용량이 pypy3가 python3보다 많았다!
문제에서 메모리제한이 너무 낮아서 메모리 초과가 계속 발생했는데
같은 코드를 python3로 돌리니 통과했다.

시간 : pypy3 > python3
메모리 사용량 : pypy3 < python3 기억하자 !!

좋은 웹페이지 즐겨찾기