[Python] 10989번 수 정렬하기3

문제

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

풀이과정

• 정렬하는 문제이지만 시간제한이 5초이고 메모리 제한이 8MB 시간이 널널하지만 메모리효율을 따져야한다. 항상 사용하던 방식으로 정렬하면 메모리초과가 발생했다.
  
• 방법을 찾아보니 계수정렬이 존재했다. 이 방법은 메모리 초과는 해결되지만 시간초과가 발생할 수 있다.
  • 많은 입력을 받을 수 있을만큼 배열을 만들고
  • 입력받을 때 마다 그 수에 해당하는 인덱스에 +1을 해주어 값으로 그 수의 개수를 담는다.
  • 다시 배열을 돌면서 값만큼 인덱스에 해당하는 숫자를 출력해준다.
• 첫 시도

  import sys
  n = int(sys.stdin.readline())
  n_list = [0]*(n+1)  # n+1개의 리스트 생성
  
  for _ in range(n):
      # 입력받을 때 마다 그 수에 해당하는 인덱스에 +1을 해주어 값으로 그 수의 개수를 담는다.
      n_list[int(sys.stdin.readline())-1] += 1
  
  for i in range(n):
      if n_list[i] != 0:
          for j in range(n_list[i]):
              print(i+1)

  처음 시도해봤는데 메모리 초과가 발생했다.
  
• 정답

  ```python
  import sys
  n = int(sys.stdin.readline())
  n_list = [0] * 10000  # 수에 해당하는 index를 담기 위해
  
  for _ in range(n):
      # 입력받을 때 마다 그 수에 해당하는 인덱스에 +1을 해주어 값으로 그 수의 개수를 담는다.
      n_list[int(sys.stdin.readline())-1] += 1
  
  for i in range(10000):
      if n_list[i] != 0:
          for j in range(n_list[i]):
              print(i+1)
  ```

  for문 내에 append를 사용하면 메모리 재할당이 이루어지기 때문에 다른 방식으로 접근해야했다.
  메모리: 31256KB
  시간: 9336ms