[백준] 10989번 수 정렬하기3(with python)

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

10989번: 수 정렬하기 3

 

1. 내가 작성한 코드

N = int(input())

arr = [int(input()) for _ in range(N)]

arr.sort()

for i in range(N):
  print(arr[i])

전 문제와 상당히 흡사해서 '이정도는 쉽지'라고 생각하며 풀었는데, 메모리 초과로 틀렸다 😥

 

2. 틀린 이유

 

내가 작성한 코드처럼 새로운 리스트를 정의해서 하나씩 입력값을 삽입하면 메모리 재할당이 이루어진다.

 

본 문제는 1,000,000만과 같이 큰 입력값과 8MB라는 메모리 제한이 있었기 때문에 '메모리 초과'등의 문제를 겪은 것

 

3. 해결 방법

https://velog.io/@yje876/python%EB%B0%B1%EC%A4%80DP-10989-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-3

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

위의 VELOG를 참고해서 코드를 작성하면 된다. 

 

-> 이러한 방법을 "계수정렬"을 이용한다고 한다 (참고로 시간복잡도는 O(n))

-> 이를 이용하면 메모리초과를 해결할 수 있으나, 시간 초과를 해결할 수는 없기 때문에 input() 대신 sys.stdin.readline()을 이용한다.

 

 

❗input()과 sys.stdin.readline()의 차이

• sys.stdin.readline()을 사용하기 위해서는 sys 라이브러리를 import 해줘야 한다.
• input() 은 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느림
• sys.stdin.readline() 은 prompt message을 파라미터로 받지 않으며, 개행 문자를 포함하여 반환함 

 

이렇게 까지 했는데 또 메모리 초과가 발생한다 띠용?! 아마 pypy3를 이용해서 그런 것 같아 python3 로 바꿔 채점을 해주니 드디어 성공!

 

❗시간이 부족할 때 => pypy3 이용, 메모리가 부족할 때 python3 이용

 

4. 모범답안

import sys

N = int(sys.stdin.readline())
arr = [0] * 10001  #0부터 10000까지 이기 때문에 10001개

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

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

 

아 얼른 알고리즘 진도 나가긴 해야겠다 ㅜㅜ