백준 알고리즘 23235번
백준 알고리즘 23235번 The Fastest Sorting Algorithm In The World
문제
정렬 알고리즘은 점근 속도를 기준으로 비교하는 것이 일반적입니다. 선택 정렬과 같은 일부 느린 알고리즘은 N개의 항목을 정렬하는 데 O(N2) 시간이 걸리는 반면, 병합 정렬과 같은 비교 기반 정렬은 합리적인 가정 하에 O(N long(N)) 시간 보다 빠를 수 없습니다. 비교 기반 정렬이 아닌 버킷 정렬은 O(N) 시간 내에 정렬할 수 있습니다. 버킷 정렬은 가능한 값의 범위가 N에 비해 작다고 가정하기 때문입니다. 일반적으로 정렬 알고리즘의 속도는 정렬하는 데이터에 대해 취할 수 있는 가정에 따라 달라집니다.
빠른 속도에도 불구하고 종종 간과되는 정렬 알고리즘 중 하나는 세계에서 가장 빠른 정렬 알고리즘입니다. 이 알고리즘은 O(1), 즉 상수 시간 내에 정렬합니다. 물론 이 알고리즘은 입력이 빠른 액세스 메모리에 있는 배열이고 입력이 이미 정렬되어 있다고 가정합니다. 이 문제를 해결하기 위해 세상에서 가장 빠른 정렬 알고리즘을 구현합니다.
입력
입력 파일에는 정렬할 배열을 설명하는 여러 테스트 케이스가 포함되어 있습니다. 각 배열 설명은 0 < N <= 100의 정수로 시작합니다. 그 뒤에는 정렬할 정수가 N 개 잇으며, 이 정수는 감소하지 않는 순서로 주어집니다. 정렬할 모든 정수는 0에서 100000 범위 내에 있습니다. 마지막 테스트 케이스 뒤에는 0이 하나 포함된 줄이 이어집니다.
출력
각 테스트 케이스에 대해 케이스 번호(1로 시작)와 정렬 완료… 라는 텍스트를 출력합니다.
예제
| 입력 | 출력 |
|---|---|
5 21 44 48 48 64 6 8 19 22 49 53 62 8 5 9 14 17 24 25 27 61 4 13 21 28 35 5 31 38 44 49 60 0 | Case 1: Sorting... done! Case 2: Sorting... done! Case 3: Sorting... done! Case 4: Sorting... done! Case 5: Sorting... done! |
풀이
num = 1
while True:
n = input()
if n == "0":
break
print(f"Case {num}: Sorting... done!")
num += 1
