문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

www.acmicpc.net/problem/2751

  • 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

  • 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

과정

아니 오랜만에 이렇게 쉬운 문제라니!!하면서 풀었는데 역시 또 틀림. 시간초과 떴다.

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
for x in sorted(arr):
    print(x)

파이썬 내장 함수가 느려서 그런가?.. 싶었지만 그건 아니었다.

최종 코드

파이썬 정렬 내장 함수의 시간복잡도는 O(NlogN) 이라서 따로 정렬 알고리즘을 구현해야하는 문제는 아니었다. 내 코드도 pypy3에서 구동하면 통과된다고 하는데 평소에 쓰던 python3에서도 통과되기 위해서 답을 찾아보았다.

문제는 정렬 알고리즘이 아니라 입력에 있었다. input 함수는 느려서 대신에 sys.stdin.readline 함수를 사용해야 한다.

import sys

n = int(sys.stdin.readline())
arr = [int(sys.stdin.readline()) for i in range(n)]

for x in sorted(arr):
    print(x)

이 코드를 주피터에서 돌렸는데 자꾸 ValueError: invalid literal for int() with base 10: '' 이런 에러가 떠서 검색해보니까 주피터에서는 readline 함수를 사용할 수 없다고 한다. prompt에서 입력을 받는 함수가 아니라서 그런 것 같다.

추가적으로 설명을 덧붙이자면 readline 함수는 한 line을 입력 받는데, ‘\n’ 개행문자까지 포함해서 저장하는 함수이다.

개행문자를 제거하기 위해서는 strip이나 rstrip함수를 사용하면 된다.

참고 사이트