Algorithm / 베스트앨범

문제

프로그래머스 / 베스트앨범

1) 문제 풀이

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var played = [String: Int]()
    var music = [String: [(n: Int, play: Int)]]()
    var answer = [Int]()
    
    for i in genres.indices {
        let genre = genres[i]
        let play = plays[i]
        
        played[genre, default: 0] += play
        music[genre, default: []].append((i, play))
    }
    
    for (genre, _) in played.sorted(by: { $0.value > $1.value }) {
        let albums = music[genre]!.sorted {
            if $0.play == $1.play {
                return $0.n < $1.n
            }
            return $0.play > $1.play
        }.prefix(2)
        
        for album in albums {
            answer.append(album.n)
        }
    }
    
    return answer
}

결과

2) 코드 개선

🚨 문제점 분석

• played.sorted(by:)의 불필요한 정렬
  • played 딕셔너리는 장르 수만큼만 존재함.
  • 만약 genres의 크기가 크지 않다면 문제 없지만, 장르 수가 많을 경우 매번 정렬하는 것이 비효율적 => O(g log g)
• music[genre]!.sorted부분의 중복 정렬
  • music[genre]의 각 리스트를 정렬할 때마다 새로운 배열을 만듦.
  • Swift의 sorted는 새로운 배열을 반환하므로 메모리 복사가 발생 → 메모리효율 저하
  • 또, .prefix(2)를 위해 전체 정렬을 수행하는 것은 낭비.
• music[genre]의 강제 언래핑
  • 논리적으로는 안전하지만, 런타임 에러 위험이 있으므로 더욱 안전한 방법을 사용하는 것이 좋음

✅ 개선 포인트

• 장르별 총합을 [(genre, playCount)] 형태로 바로 만들어두고, 한 번만 정렬 수행
• music[genre]의 상위 2개만 필요하므로 partial sort(2개만 찾기)로 최적화
• if let, guard let을 통한 안전한 옵셔널 바인딩 사용.

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var genrePlayCount = [String: Int]()
    var songsByGenre = [String: [(index: Int, play: Int)]]()
    var result = [Int]()
    
    for i in genres.indices {
        let genre = genres[i]
        let play = plays[i]
        
        genrePlayCount[genre, default: 0] += play
        songsByGenre[genre, default: []].append((i, play))
    }
    
    let sortedGenres = genrePlayCount.sorted { $0.value > $1.value }
    
    for (genre, _) in sortedGenres {
        guard let songs = songsByGenre[genre] else { continue }
        
        let topTwo = songs.sorted {
            $0.play == $1.play ? $0.index < $1.index : $0.play > $1.play
        }.prefix(2)
        
        result.append(contentsOf: topTwo.map { $0.index })
    }
    
    return result
}

결과