이번 포스트에서는 스위프트를 활용한 코딩테스트에서 자주 출제되는 정렬 문제에 대해 다루어 보겠습니다. 특히, ‘수 정렬하기 2’ 문제를 통해 정렬 알고리즘의 기초와 실제 코딩테스트에 어떻게 응용되는지 알아볼 예정입니다.
문제 설명
주어진 수 N개의 배열을 오름차순으로 정렬하여 출력하시오. N은 1,000,000보다 작거나 같은 자연수이며, 배열의 각 수는 1,000,000보다 작거나 같고, 0보다 크거나 같은 정수입니다.
입력:
5
5
4
3
2
1
출력:
1
2
3
4
5문제 해결 접근법
이 문제는 기본적인 정렬 알고리즘의 이해와 구현을 요구합니다. 그러나 제한된 시간과 메모리를 고려할 때, 가장 효율적인 방법으로 정렬을 수행해야 합니다. 일반적으로 O(N log N)의 시간 복잡도를 가지는 정렬 알고리즘인 퀵 정렬, 병합 정렬 또는 힙 정렬을 고려할 수 있지만, 이 문제에서는 수의 범위가 제한적이므로 카운팅 정렬을 활용하는 것이 효율적입니다.
카운팅 정렬
카운팅 정렬은 정렬할 데이터의 범위가 한정되어 있을 때 유용하게 사용됩니다. 주어진 수의 범위가 0부터 1,000,000까지이고 중복된 수가 있을 수 있으니, 각 수의 개수를 세어서 정렬된 결과를 생성할 수 있습니다. 카운팅 정렬은 다음과 같은 단계를 따릅니다:
- 입력된 수의 최대값을 확인하여 배열의 크기를 결정한다.
- 0부터 최대값까지의 인덱스를 가지는 카운팅 배열을 초기화 한다.
- 입력된 수를 읽어 각 수에 해당하는 인덱스에 1씩 더한다.
- 카운팅 배열을 참조하여 정렬된 결과를 출력한다.
스위프트 구현
이제, 위의 접근법을 바탕으로 스위프트로 코드를 작성하겠습니다.
import Foundation
let n = Int(readLine()!)!
var numbers = [Int](repeating: 0, count: 1000001)
// 입력 값 저장
for _ in 0.. 0 {
for _ in 0.. 코드 설명
위 코드를 설명하겠습니다:
- `let n = Int(readLine()!)!`로 첫 줄에서 입력되는 수의 개수를 읽어옵니다.
- `var numbers = [Int](repeating: 0, count: 1000001)`로 0부터 1,000,000까지의 수를 저장할 카운팅 배열을 생성합니다.
- `for _ in 0..
- 마지막으로, 이중 루프를 통해 카운팅 배열을 순회 후 결과를 출력합니다. 숫자가 몇 번 나왔는지를 기반으로 출력합니다.
복잡도 분석
이번 문제의 시간 복잡도는 O(N)이며, 공간 복잡도는 O(K)입니다(여기서 K는 입력 수의 범위, 즉 1,000,001입니다). 따라서 입력 수가 많아도 효율적으로 처리할 수 있습니다.
마무리하며
이번 포스트를 통해 수 정렬하기 2 문제를 해결하는 방법으로 카운팅 정렬을 활용해 보았습니다. 카운팅 정렬은 데이터의 범위가 한정되어 있을 때 매우 유용하니 기억해 두시기 바랍니다. 다양한 정렬 알고리즘에 대한 이해도를 높이는 것도 시간을 단축시키고 더 나은 코드를 작성하는 데 도움이 됩니다. 다음 포스트에서는 다른 알고리즘 문제를 다루어 보도록 하겠습니다!