백준 알고리즘 10989번 수 정렬하기3 Swift

문제

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

 

 

단순히 정수의 정렬이라고 생각하여 Swift의 sorted() 메소드를 사용하여 풀었으나 결과는 시간초과...

let count = Int(readLine()!)!

var numbers = [Int]()
while let line = readLine() {
    numbers.append(Int(line)!)
}

var result = ""
for number in numbers.sorted() {
    result += "\(number)\n"
}

print(result)

 

계수 정렬

정수를 정렬해주는 알고리즘을 나무위키에서 찾아보던 중 현재의 조건에 맞는 가장 빠른 방법을 찾았다.

 

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-4.4.2

 

조건: 데이터(정수)의 최댓값 k가 크지 않을 경우

시간복잡도: O(n + k)

 

예시:

    let 최댓값k = 10
    let 정렬할배열 = [1, 3, 7, 5, 2, 3, 1, 5]
    var 결과 = [Int]()

	1. 1에서 10까지의 카드를 나열한다.
	2. 정렬할 배열에서 앞에서부터 정수를 하나씩 꺼내서 정수와 일치하는 숫자의 카드에 개수를 적는다.
	3. 카드에 적힌 개수대로 결과배열에 카드의 숫자를 넣는다.

 

 

코드

(참고: https://dev-mandos.tistory.com/130)

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 {
    result += String(repeating: "\(i)\n", count: cards[i])
}

print(result)

 

정리

Swift에 API가 많기도 하고, 불편함을 못느꼈다보니, 여지껏 알고리즘의 중요성을 잘 몰랐던 것 같다.

CS50강의를 들을때도 이런 것도 있구나 하고 넘어갔었는데, 알고리즘을 풀어보며 그 중요성과 필요성을 깨닫게 됐다.

 

참고

정렬 알고리즘

계수 정렬 - 위키백과, 우리 모두의 백과사전

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

[Swift] 10989 : 수 정렬하기 3