안녕하세요! 이번에는 스위프트를 기반으로 한 코딩테스트 문제인 “수 정렬하기 3″를 함께 풀어보겠습니다. 이 문제는 간단하게 숫자를 정렬하는 것처럼 보이지만, 특정한 조건과 제약이 있어서 코딩테스트에서는 좋은 연습이 될 것입니다. 이번 글에서는 문제 정의와 입력, 출력 형식, 알고리즘적 접근 방법, 그리고 최적화 방법에 대해 자세히 알아보겠습니다.
문제 설명
문제의 요구 사항은 주어진 수들을 정렬하되, 정렬할 수의 범위가 제한되어 있다는 것입니다. 구체적으로, 수의 범위는 1 이상 100,000 이하의 정수이며, 이 정수를 오름차순으로 정렬하여 출력하는 것입니다.
예를 들어, 다음과 같은 수들이 주어진다고 가정해보겠습니다:
- 5
- 3
- 8
- 1
- 2
이 경우, 출력은 다음과 같이 표시되어야 합니다:
- 1
- 2
- 3
- 5
- 8
입력 형식
입력은 다음과 같은 형식으로 제공됩니다:
- 첫 번째 줄에 숫자의 개수
N이 주어집니다. (1 ≤ N ≤ 100,000) - 두 번째 줄에는
N개의 정수가 공백으로 구분되어 주어집니다.
출력 형식
출력은 정렬된 수를 한 줄에 하나씩 출력해야 합니다.
풀이 접근
이 문제는 우리가 수를 정렬하는 것이기 때문에, 가장 기본적인 정렬 알고리즘을 사용할 수 있습니다. 하지만, N의 최대 값이 100,000이므로, O(N^2) 시간 복잡도를 가진 Bubble Sort나 Selection Sort 같은 비효율적인 알고리즘은 사용할 수 없습니다.
여기서는 Counting Sort 알고리즘을 이용하여 문제를 해결하고자 합니다. Counting Sort는 주어진 수의 범위가 제한되어 있을 때, 더욱 효율적으로 정렬할 수 있는 방법입니다. 이 알고리즘은 다음과 같은 단계를 거칩니다:
- 입력된 수의 범위에 해당하는 배열을 생성합니다.
- 입력 수의 등장 횟수를 해당 인덱스에 기록합니다.
- 최종적으로, 등장 횟수에 따라 정렬된 수를 출력합니다.
코드 구현
이제 스위프트로 문제를 해결하기 위한 코드를 작성해보겠습니다. 스위프트에서는 배열을 필드로 사용할 수 있기 때문에, Counting Sort를 구현하기가 매우 수월합니다. 아래는 그 구현 예시입니다:
import Foundation
func countingSort(numbers: [Int]) -> [Int] {
// 수의 범위가 1~100,000이므로 100,001 크기의 배열 초기화
var counts = Array(repeating: 0, count: 100001)
// 각 수의 개수를 카운트
for number in numbers {
counts[number] += 1
}
var sortedNumbers: [Int] = []
// 카운트를 기반으로 정렬된 수 생성
for (number, count) in counts.enumerated() {
for _ in 0..실행 예제
위의 코드를 사용하여 입력을 해봅시다. 예를 들어, 다음과 같은 입력을 제공한다고 가정합니다:
5
5 3 8 1 2
출력 결과는 다음과 같아야 합니다:
1
2
3
5
8
복잡도 분석
이 알고리즘의 시간 복잡도는 O(N + K)입니다. 여기서 N은 입력되는 수의 개수, K는 수의 범위입니다. 이 경우 K는 100,000으로 고정되어 있으므로, 알고리즘이 매우 효율적이라고 할 수 있습니다. 공간 복잡도 역시 O(K)개소가 필요하므로 O(100,000) 공간을 차지합니다.
마치며
이번 글에서는 “수 정렬하기 3″라는 문제를 살펴보았고, Counting Sort를 이용한 해결 방법을 구현했습니다. 이와 같은 수 정렬 문제는 기본적인 알고리즘의 이해도를 높이고, 실제 코딩테스트에서 자주 등장할 수 있는 주제이므로 반드시 연습해보시길 바랍니다. 다음 강좌에서는 더 어려운 문제에 도전해보겠습니다. 감사합니다!