수 정렬하기 3 - 10989번

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

풀이

같은 문제: 2750번, 2751번 | 메모리제한이 256mb에서 8mb
arr내의 수는 10,000보다 작거나 같은 자연수이다.

import sys
input = sys.stdin.readline
n = int(input())
arr = [0]*10000

# 오답 - 입력값 중 중복되는 경우를 무시하고 있다.
# for _ in range(n):
#   val = int(input())
#   arr[val] = val

# for i in range(0, 10000-1):
#   if arr[i]!=0:
#     print(i)

# 정답
for _ in range(n):
  inpval = int(input())
  arr[inpval-1]+=1

for i in range(0, 10000):
  if arr[i]!=0:  				# i == inpval-1
    for _ in range(arr[i]):
      print(i+1) 				# i+1 == inpval

접근 방식은, 배열의 value를 sorted()하는 것이 아닌 배열 요소의 index를 가져 오겠다는 것이다.

우선
10,000개의 [0]로만 구성된 '비어있는 바구니' 배열을 선언한다.
빈 바구니 배열 arr의 인덱스 값은 0~10000-1이다.

import sys
input = sys.stdin.readline
n = int(input())
arr = [0]*10000

-> 주어진 입력값 중 하나인 숫자 inpval를, 빈 배열의 inpval-1번째 요소의 값으로 +=1 씩 증가. 이제 arr[inpval-1]은 곧 [1]이며, print(arr[inpval-1]) == 1 이다.
계속 그럴 진 모른다. 숫자 inpval은 중복되어 입력될 수도 있기 때문이다.
inpval의 중복되는 갯수만큼 arr[inpval-1]는 그 값이 추가 +1 된다.

예를 들어,
입력값 중 3이 5번 있었다면 최종적으로 arr[2]==5 가 된다.

for _ in range(n):
  inpval = int(input())
  arr[inpval-1]+=1

그럼 이제 arr는 드문드문 값이 있는 요소들이 있는, 인덱스 0~9999까지의, 요소 10000개를 가진 '거의 빈 바구니' 배열이다.

-> 이후 다시 for문으로 '거의 빈 바구니' 배열인 arr에 접근한다.
이 for문의 i값은 0~9999의 범주를 돌 것이다.

for i in range(0, 10000):
	if arr[i] ....
    .
    .
    .

여기서 arr[i]의 "i" == inpval-1 과 같다.

arr 중 값이 0이 아닌 요소들의 인덱스 값+1을 그 요소의 값만큼 즉 해당 inpval의 입력 횟수번만큼 출력한다.
(여기서 for문의 i는 당연한 얘기지만 0부터 9999까지 차례대로 올라가므로 우리가 출력시킬 arr의 요소 인덱스 값 역시 오름차순이 된다. 문제의 의도대로.)

if arr[i]!=0:
    for _ in range(arr[i]):
      print(i+1)

i+1 == inpval이다.

예를 들면,
arr[2]!=0 이므로 (이 요소의 인덱스+1)==inpval==3이 출력될 것이다.
그리고 이것은 해당 inpval의 입력 횟수번 즉 (즉 이 요소의 값)만큼 반복시킬 거다.
arr[2]==5이므로 3은 터미널에 다섯 번 찍힌다.

for문 안의 for문으로, range(arr[2]) 즉 range(5) \n print(i+1)
다시 말하면 i+1은 곧 아까 처음의 inpval과 같은 수가 된다.