[BOJ/백준] Swift - 수 정렬하기 3 (10989)

 

 

 

수 정렬하기 1,2 처럼 내장 함수로 꿀빨려다가 시간초과 나온 문제.

계수정렬로 풀어야 하는 게 핵심이었던 문제다. 

하지만 아직 계수정렬 공부하지 못한 상태라?

후다닥 뒤져보면서 풀어봤다.

 

 

 

계수 정렬(Counting Sort)란?

• 각 숫자의 등장 횟수를 저장한 후, 그 정보를 기반으로 정렬하는 방법
• 숫자의 범위가 제한적인 경우(예: 1 ~ 10,000)에 매우 빠르게 동작
• 비교 기반 정렬(퀵 정렬, 병합 정렬)보다 O(n + k) 의 시간 복잡도를 가지므로 특정 상황에서는 더 효율적
• 하지만 메모리를 많이 차지(입력 크기보다 훨씬 큰 배열을 만들어야 함)

 

 

수 정렬하기 3 (10987)

문제링크 :https://www.acmicpc.net/problem/10989

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

 

    let n = Int(readLine()!)!
    var cards = [Int](repeating: 0, count: 10001)

    for _ in 0..<n {
        cards[Int(readLine()!)!] += 1
    }

    var result = ""

    for i in 1...10000 {
        if cards[i] > 0 {
            result.append(String(repeating: "\(i)\n", count: cards[i]))
        }
    }

    print(result)

 

 

 

• 크기가 10,001인 배열 cards를 생성 (1~10,000까지 숫자를 저장)
• cards[i]는 숫자 i가 입력된 개수를 의미
• repeating: 0 → 배열을 모두 0으로 초기화

 

 

 

계수 정렬의 시간 복잡도

• 입력 처리 (숫자 카운팅): O(n)
• 출력 처리 (결과 생성 및 출력): O(n + k)
  • k는 숫자의 범위 (1 ~ 10000 이므로 k = 10000)
• 전체 시간 복잡도: O(n + k) → 매우 빠름!