수 정렬하기2

내가 작성한 코드

import sys
input=sys.stdin.readline

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

고려사항

• 시간 초과 : 2750번 백준 문제와 정말 유사하지만 시간 초과를 내지 않기 위한 방법이 필요했다.

  처음에는 앞서 풀었던 방식인 삽입 정렬 방식은 시간 초과를 해결할 수 없었다.
  퀵 정렬을 직접 구현하고 풀었어도 시간 초과의 벽에 부딪혔다.
  python 내장 함수인 sort를 사용하였어도 시간초과가 발생했다.
  이 분제를 해결하기 위해선 입력 받고 처리하는 시간을 줄이는 방법이 필요했다.

해결 방법

아래의 코드를 추가하여 input()을 sys.stdin.readline()으로 바꾸어준다.

import sys
input=sys.stdin.readline

그냥 input() 내장함수를 사용하는 것은 sys.stdin.readline()과 다른 역할을 한다.

input()

• parameter로 prompt message를 받을 수 있기 때문에 입력 받기전 prompt message를 출력해야한다.
  이때 prompt message가 없더라고 약간의 부하가 생긴다.
• 입력받은 값의 개행 문자를 삭제시키며 리턴한다. 즉 문자열에 rstrip()함수를 적용시키며 리턴하기 때문에 부하가 발생한다. 지금 문제에선 숫자를 하나씩 많은 수를 입력받는데 이때마다 rstrip()을 적용시키는 부하가 발생한다.
  반면에 sys.stdin.readline()은 개행문자를 포함한 값을 리턴한다.

예외 사항들

• 퀵정렬을 직접 구현하고 sys.stdin.readline()을 적용시켰지만 60%정도 에서 시간초과가 발생했다.
  그 이유는 퀵 정렬을 하더라도 최대 n^2의 시간 복잡도를 갖을 수 있기 때문이다.
  srot()같은 내장함수는 퀵정렬 기반으로 이루어져있지만, 내부 알고리즘으로 최적화를 하여 직접 구현한 것 보다 더 효율 적이게 동작한다고 한다.
• runtime type error 발생

  	for a in arr.sort():
    	 		print(a)

  출력문을 이렇게 작성하였더니 type error가 발생했다.
  sort() 함수의 원문 설명을 보면 아래와 같이 얘기하고 있다.

  You can also use the list.sort() method. It modifies the list in-place (and returns None to avoid confusion). Usually it’s less convenient than sorted() - but if you don’t need the original list, it’s slightly more efficient.

  혼동을 피하기 위해서 None을 리턴한다고 한다. arr list 자체를 변경시키니 따로 arr을 리턴하지 않는다는 의미인것 같다. 또한 원본 list를 변경하는 것에 대해 부담이 없다면 sort가 조금 더 효율적이다 라고 애기하고 있다.

하지만 이해가 되지 않는 부분은 vscode에서는 잘 출력이 되었다는 것이다.. 어떻게 동작 할 수 있었는지,,,, ㅜㅜ
그래서 이러한 이유로 제출 코드는 sort를 실행하고 for 문 범위에 arr을 넣어주었다.

결과