S5 2751. 수 정렬하기 2

문제 보기 :  2751번: 수 정렬하기 2 (acmicpc.net)

---

문제

• 정답률 : 31%

---

작성 코드 & 풀이 과정 코멘트

1) 시간초과 났던 코드들

import heapq

T = int(input())

def sol(T):
    a = []
    for _ in range(T):
        heapq.heappush(a,int(input()))

    for _ in range(T):
        min_a = heapq.heappop(a)
        print(min_a)

처음에는 heapq로 차례대로 최소값을 출력하는 방식으로 풀이했다. 근데 시간초과 발생.. 흐규

T = int(input())
a = [int(input()) for i in range(T)]

def qsort(arr):
    if len(arr) <= 1:
        return arr
    a = arr[0] ; b = arr[1:]
    left = [x for x in b if x<a]
    right = [x for x in b if x>=a]
    return qsort(left)+[a]+qsort(right)

arr = qsort(a)
print(*arr,sep='\n')

두번째 방법으로는 quicksort 함수를 구현해둔 뒤 재귀로 풀이해봤는데,
음.. 굳이 이걸 구현하는게 필요할까? 싶기도 했고
혹시나 해서 제출해봤는데 역시나 시간초과가 발생했다

T = int(input())
a = [int(input()) for i in range(T)]
a.sort()
for i in a:
    print(i)

quicksort() 대신 가장 정석적인 sort로 썼는데, for문 때문인건지 또 시간초과 ㅠ^ㅠ

import sys
input = sys.stdin.readline()

T = int(input)
a = [int(input) for i in range(T)]
a.sort()
print(*a,sep='\n')

sys 라이브러리를 사용해 약 1,000,000개의 숫자들을 읽어오고,
문자열은 각각 다른 줄에 분리해서 출력하도록 코드를 짰는데..
도대체 웨.. 이것도 시간초과인거니

---

2) 패스 답안

import sys

T = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for i in range(T)]
a.sort()

answer = '\n'.join(map(str,a))
print(answer)

드디어 찾은 답안은 이거다.
아예 join함수로 답을 문자열로 바꿔서 출력하는 것인데 대신 좀 기~~인 답이랄까?

근데 코딩테스트 문제에는 이런 문제는 잘 안나와서.. 중요할까 싶다!