[BJ] 수 정렬하기3

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

 

import sys

N = int(input())

arr = [int(sys.stdin.readline().strip()) for _ in range(N)]

arr.sort()

print("\n".join(map(str,arr)))

 

시간 초과 문제가 발생한다

 

1. sort 함수 사용

2. input() 사용

 

등의 이유라고 함

 

이를 해결하기 위해서는,

 

import sys

# 입력 빠르게 받기
input = sys.stdin.readline

# 입력받기
N = int(input())  
count = [0] * 10001  # 1부터 10,000까지 등장 횟수 저장

# 숫자 카운트
for _ in range(N):
    num = int(input())
    count[num] += 1

# 정렬된 값 출력
for i in range(10001):  # 1부터 10,000까지 순회
    if count[i] > 0:
        for _ in range(count[i]):  
            print(i)

 

 

이 문제는 **계수 정렬(Counting Sort)**을 사용하면 빠르게 해결할 수 있습니다.
주어진 수의 범위가 10,000 이하의 자연수이므로, 등장 횟수를 저장하는 배열을 활용한 정렬이 효율적입니다.

---

🔹 해결 방법 (계수 정렬)

1. 입력값을 배열에 저장
   • 숫자의 개수를 저장할 크기 10,001짜리 배열(count)을 생성 (count[i]는 숫자 i의 등장 횟수).
2. 입력된 숫자를 count 리스트에 카운트
   • 입력받은 숫자의 등장 횟수를 증가시킴 (count[num] += 1).
3. count 리스트를 순회하면서 정렬된 값 출력
   • i가 count[i]만큼 등장했으므로 해당 횟수만큼 출력.

 

---

1. 입력 속도 최적화
   • sys.stdin.readline()을 사용하여 빠르게 입력받음 (일반 input()보다 빠름).
2. 계수 정렬 방식 적용
   • count[i]에 숫자 i의 등장 횟수를 저장.
   • 이후, count[i]가 0보다 크면 해당 횟수만큼 i를 출력.
3. 메모리 효율성
   • 입력값이 10,000 이하의 자연수이므로, 최대 10001 크기의 리스트만 사용하면 됨.
   • 공간 복잡도: O(K) (K=10,000)
     → N=10,000,000여도 문제없이 실행 가능!
4. 시간 복잡도
   • 입력 처리: O(N)
   • 출력 처리: O(K + N)
   • 총 시간 복잡도: O(N + K) → 매우 빠름!