Seongkyun Han's blog

190130 백준 알고리즘 문제풀기*

30 Jan 2019 | baekjoon

[10989] 수 정렬하기 3*

문제

  • 주어진 수를 오름차순으로 정렬하되, 카운팅이나 기수 정렬을 사용

  • 문제를 다양한 방법으로 풀도록 수없이 접근했으나.. 시간초과 혹은 메모리 초과 오류가 발생한다.

정답 (메모리 초과)

def counting_sort(A, k):
    B = [-1] * len(A)
    C = [0] * (k + 1)
    for a in A:
        C[a] += 1
    for i in range(k):
        C[i+1] += C[i]
    for j in reversed(range(len(A))):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1
    return B
a = []
MAX_NUM = 10000
for _ in range(int(input())):
    a.append(int(input()))
result = counting_sort(a, MAX_NUM)
for j in range(len(result)):
    print(result[j])
  • 카운팅 정렬을 사용한다.
  • 입력은 메모리 절약을위해 input() 메소드가 아닌 sys.stdin.readline()을 사용한다.
  • print('%s\n'%i*p[i],end='')
    • ("%s\n"%i)*p[i]과 동일하며, print(5*"\n")시 5 줄이 개행되는것과 동일함
  • 각 수가 들어있는 갯수인 10,001개의 배열(list) p를 설정한다
    • 갯수가 10,001개인거는 이렇게 해야 빠르다고…한다는데 이유는 잘 모르겟다..
  • 다음으로 설정된 배열 p에 해당하는 숫자들을 입력 숫자에 따라 1씩 카운팅한다.

  • 카운팅 된 수에 해당하는 숫자중 적은 숫자의 인덱스를 출력한다.

  • 정말 까다로운 문제였다.. 메모리초과와 시간초과때문에….

정답

import sys
m=10000
p=[0]*(m+1)
t=int(sys.stdin.readline())
for i in range(t):
    p[int(sys.stdin.readline())]+=1
for i in range(m+1):
    print('%s\n'%i*p[i],end='')

Related Posts