[BOJ/백준] Swift - 단어정렬 (1181)

 

 

 

단어정렬 (1181)

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

단어의 순서를 정의하여 정렬하는 문제

 

    let n = Int(readLine()!)!
    var words: [String] = []
    
    for _ in 0..<n {
        let input = readLine()!
        words.append(input)
    }
    
    var seen = Set<String>()
    var uniqueWords = words.filter { seen.insert($0).inserted }
    uniqueWords.sort { $0.count == $1.count ? $0 < $1 : $0.count < $1.count }
        
    for word in uniqueWords {
        print(word)
    }

 

 

 

 

• 좀 더 최적화된 코드

let n = Int(readLine()!)!
var uniqueWords = Set<String>()

// 중복을 제거하면서 입력받기
for _ in 0..<n {
    uniqueWords.insert(readLine()!)
}

// 정렬 (길이 우선, 동일하면 사전순)
let sortedWords = uniqueWords.sorted { $0.count == $1.count ? $0 < $1 : $0.count < $1.count }

// 결과 출력
for word in sortedWords {
    print(word)
}

 

 

 

그러나 ? 

 

 

 

위가 최적화, 아래가 기존 작성 코드라 했을때 

 

시간복잡도는 O(nlogn)으로 동일하며, 

메모리 사용량에서는 최적화 < 기존

시간 순에서는 기존 < 최적화 

코드길이에서는 기존 > 최적화

로 차이를 보였다. 

 

아무래도 최적화의 경우는 애초에 선언부터 중복을 없애고 시작했기때문에

비교할 데이터 양이 줄어 메모리가 낮아졌겠지만, 속도는 더 느려진 결과다. 

비교할 데이터도 적어졌는데, 왜 느려진거지 ?

궁금해서 chat찍이한테 물어봤다. 

 

array와 set성능의 차이가 주된원인.

 

속도 차이의 원인

1. 정렬 대상 데이터 크기 차이 (Array vs Set)
   • 기존 코드: Array에서 중복을 제거한 후 정렬
   • 최적화 코드: Set에서 Array로 변환 후 정렬
   ➡ Set에서 Array로 변환하는 과정이 추가되면서 오버헤드가 발생할 수 있음
2. Set의 내부 구조
   • Set은 해시 기반 자료구조이므로, 입력 순서가 보장되지 않음
   • 따라서 Array로 변환 후 다시 정렬하는 비용이 더 클 수 있음
3. Swift의 sort() 최적화
   • sort()는 내부적으로 퀵소트 기반의 최적화된 알고리즘을 사용
   • 정렬할 데이터가 이미 어느 정도 정렬된 상태라면, 기존 코드의 정렬이 더 빠를 수 있음

 

 

결론

1. 기존 코드에서는 Array 자체에서 정렬 수행 → O(n log n)
2. 최적화 코드에서는 Set → Array 변환 후 정렬 → O(n log n) + 추가적인 변환 비용
3. Set 변환이 추가되면서 오히려 더 느려질 수 있음

➡ 결론: 메모리 사용을 최적화하는 대신 속도는 기존 코드가 더 빠를 수도 있음!
✔ 속도가 중요하면 기존 코드 유지
✔ 메모리가 중요하면 최적화 코드 사용