[백준 10989] 파이썬 - 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

# 조건

• N개의 수가 주어질 때, 오름차순으로 정렬하여라.
• 첫 줄에 수의 개수 N(1<=N<=10,000,000)
• N개의 줄에 걸쳐 수가 주어진다. 이 수는, 10,000보다 작거나 같다.

 

# 접근 방법

• 단순히 정렬하는 문젠데 수를 받아준 후 sort를 이용하여 출력한다면 메모리초과 발생
• 배열을 사용한 카운트 정렬 또한 메모리초과가 발생하였다.
• 메모리가 8MB 이기 때문에 배열을 사용하지 말고 바로바로 카운트를 올려주는 것이 좋아보인다. - 딕셔너리가 떠올랐다.
• 딕셔너리에 기록해두고, value만큼 반복해서 출력해주면 패스!

 

# 배열 사용 카운팅 정렬 이용

• 메모리 초과

# 카운팅 정렬
import sys  

input = sys.stdin.readline  
  
def counting():  
    for i in num:  
        counts[i] = num.count(i)  
    # 정수의 개수의 누적 합을 구해준다.  
    for j in range(1, len(counts)):  
        counts[j] += counts[j - 1]  
  
    # num 리스트를 돌며 정렬시켜준다.  
    for k in range(len(num) - 1, -1, -1):  
        # 카운팅에서 -1을 해주고  
        counts[num[k]] -= 1  
        temp[counts[num[k]]] = num[k]  
  
    return temp  
  
N = int(input())  
num = [int(input()) for _ in range(N)]  
# 계수 정렬 이용  
# 최댓값 찾아준 후  
a = max(num)  
# 정렬 시킬 리스트와 카운팅 리스트  
temp = [0] * N  
counts = [0] * (a+1)  
# 각 항목의 수 세어준다.  
  
counting()  
for i in temp:  
    print(i)

 

 

# 내 코드

import sys  
input = sys.stdin.readline  
  
N = int(input())  
  
count = {}  
for i in range(N):  
    a = int(input())  
    # 입력받으며 딕셔너리 key에 존재한다면 +1 아니면 1로 생성
    if a in count:  
        count[a] +=1  
    else:  
        count[a] = 1  
# 튜플로 키값과, 밸류값을 정렬해준 후 value값만큼 반복하며 출력
a = sorted(count.items())  
for i in a:  
    for j in range(i[1]):  
        print(i[0])

 

 

# 다른 분 코드

• 처음 10000까지의 리스트를 만들어 준 후
• 바로바로 카운트 후 출력해주었다.

import sys
n=int(input())
a=[0]*10001
for i in range(n):
  a[int(sys.stdin.readline())]+=1
for i in range(10001):
  for j in range(a[i]): print(i)