[백준] 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

< 문제 설명 >

주어진 수를 오름차순으로 정렬하면 된다.

시간 제한 : 5초, 메모리 제한 : 8MB

 

 

< 문제 이해 >

시간과  메모리 제한이 까다로워서 기본적인 정렬로는 힘들 것이라고 생각했다.

그래서 heaqp를 시도해 보았으나 실패^^

방법이 잘 떠오르지 않아 검색의 도움을 받았다*^^*

 

 

< 시행 착오 >

sort()와 heapq 모두 실패

n = int(input())

num = []

for i in range(n):
    num.append(int(input()))

num.sort()

for i in num:
    print(i)

import heapq

n = int(input())

num = []

for i in range(n):
    num.append(int(input()))

heapq.heapify(num)

for i in num:
    print(i)

 

검색을 통해 얻은 풀이 방법이다.

요 풀이는 시간 초과가 나왔다. 

n = int(input())

num = [0] * 10001

for i in range(n):
    temp = int(input())
    num[temp] += 1

for i in range(10001):
    for j in range(num[i]):
        print(i)

 

 

< 문제 풀이 >

input()을 sys.stdin.readline()을 사용했더니 통과했다.

최대 천만개의 숫자를 정렬하는 것이 힘들기 때문에

미리 크기가 10001(0~10000)인 배열을 만들고

개수를 카운트해 마지막에 개수만큼 출력하는 방식이다.

import sys

n = int(input())

num = [0] * 10001

for i in range(n):
    temp = int(sys.stdin.readline())
    num[temp] += 1

for i in range(10001):
    for j in range(num[i]):
        print(i)

 

 

다른 사람들의 여러 풀이를 보다가

마지막 for문에서 배열 속 0인 것은 제외한다는 if문을 사용한 풀이가 있었다.

더 시간이 짧게 걸릴까 해서 돌려보았다.

위의 풀이보다 시간이 더 오래 걸렸다.

import sys

n = int(input())

num = [0] * 10001

for i in range(n):
    temp = int(sys.stdin.readline())
    num[temp] += 1

for i in range(10001):
    if num[i] != 0:
        for j in range(num[i]):
            print(i)

 

 

이번에는 첫번째 for문에 temp에 할당해준 int(sys.stdin.readline())을 temp에 할당하지 않고

바로 사용하는 코드를 다시 돌려보았다.

시간이 짧아진 것을 확인할 수 있었다.

import sys

n = int(input())

num = [0] * 10001

for i in range(n):
    num[int(sys.stdin.readline())] += 1

for i in range(10001):
        for j in range(num[i]):
            print(i)

 

 

신기방기