베스트앨범

김하민·2024년 11월 22일
Lv. 3해시
1

[Swift] 프로그래머스에서 문제를 풀어보자

목록 보기
5/6
post-thumbnail

문제

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

  1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
  2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
  3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

링크

처음 든 생각

해쉬 문제니까 Dictionary 갖고 풀면 되겠다!라고 생각이 들어서,
hashMap이라는 이름의 딕셔너리 변수를 선언해주었습니다. 이렇게요:

var hashMap: [String: [Int]] = [:]

Key가 될 String에는 장르 이름이 들어가고, Value가 될 [Int]에는 노래의 인덱스, 재생 횟수 등이 들어가게 말이죠.

근데 생각해보니까 장르의 총 재생 횟수, 곡 별로 재생 횟수도 비교해야 되더라고요.

그래서 그냥 구조체를 만들었습니다 ㅎ

struct GenreDetails {
    private(set) var songs: [Song] = []
    private(set) var totalPlays: Int = 0
    
    mutating func addSong(_ song: Song) {
        songs.append(song)
        totalPlays += song.played
    }
}

struct Song {
    let played: Int
    let index: Int
}

그래서 요 구조체들이...

var hashMap: [String: GenreDetails] = [:]

요렇게 들어갈 수 있게요.

테스트나 함 돌려봅시다.

근데 [String: GenreDetails]라고 되어있으니 통일성이 좀 모자라서 마음이 불편해지네요.

Typealias를 사용해서 Genre로 String을 둔갑시켜줍니다.

typealias Genre = String

이러면 이제 String의 별칭으로 Genre를 쓸 수 있게 되구요,

var hashMap: [Genre: GenreDetails] = [:]

요런 편안하고 깔끔한 코드가 되게 됩니다.

그 뒤로는 그냥 문제 읽으면서... 적절히 코드를 작성해줬구요.

아래의 코드가 나왔습니다.

코드

import Foundation

typealias Genre = String

struct GenreDetails {
    private(set) var songs: [Song] = []
    private(set) var totalPlays: Int = 0
    
    mutating func addSong(_ song: Song) {
        songs.append(song)
        totalPlays += song.played
    }
}

struct Song {
    let played: Int
    let index: Int
}

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var hashMap: [Genre: GenreDetails] = [:]
    var result: [Int] = []
    
    for index in 0..<genres.count {
        let song = Song(played: plays[index], index: index)
        hashMap[genres[index], default: GenreDetails()] .addSong(song)
    }
    
    let sortedByTotalPlays = hashMap.sorted { (first, second) in
        return first.value.totalPlays > second.value.totalPlays
    }
    
    for genre in sortedByTotalPlays {
        
        switch genre.value.songs.count {
        case 1: result.append(genre.value.songs[0].index)
        case 2:
            let first = genre.value.songs[0]
            let second = genre.value.songs[1]
            
            if first.played > second.played {
                result.append(first.index)
                result.append(second.index)
            } else if first.played < second.played {
                result.append(second.index)
                result.append(first.index)
            }
        case 3...:
            var inOrder = genre.value.songs.sorted { $0.played < $1.played }
            
            let last = inOrder.popLast()
            let secondLast = inOrder.popLast()
            
            result.append((last?.index)!)
            result.append((secondLast?.index)!)


        default: print("error")
        }
    }

    return result
}

테스트도?

통과하는군요.

그럼 이대로 채점까지 ㄱㄱ합시다.

그런데...

넌 못지나간다를 시전하는 프로그래머스씨...

않이외않돼는거야

빡침을 잠시 가라앉히고 문제를 다시 읽어보고 옵시다...

간과한 것

  1. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

신나게 문제 푸느라 마지막 기준을 그냥 무시해버려서... 안되었던 것입니다...

그래도 조건문 몇 개만 추가해주면 되니 얼른 가서 고치고 옵시다.

고친 코드

import Foundation

struct GenreDetails {
    private(set) var songs: [Song] = []
    private(set) var totalPlays: Int = 0
    
    mutating func addSong(_ song: Song) {
        songs.append(song)
        totalPlays += song.played
    }
}

struct Song {
    let played: Int
    let index: Int
}

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var hashMap: [String: GenreDetails] = [:]
    var result: [Int] = []
    
    for index in 0..<genres.count {
        let song = Song(played: plays[index], index: index)
        hashMap[genres[index], default: GenreDetails()] .addSong(song)
    }
    
    let sortedByTotalPlays = hashMap.sorted { (first, second) in
        return first.value.totalPlays > second.value.totalPlays
    }
    
    for genre in sortedByTotalPlays {
        
        switch genre.value.songs.count {
        case 1: result.append(genre.value.songs[0].index)
        case 2:
            let first = genre.value.songs[0]
            let second = genre.value.songs[1]
            
            if first.played > second.played {
                result.append(first.index)
                result.append(second.index)
            } else if first.played < second.played {
                result.append(second.index)
                result.append(first.index)
            } else if first.index < second.index {
                result.append(first.index)
                result.append(second.index)
            } else if first.index > second.index {
                result.append(second.index)
                result.append(first.index)
            }
        case 3...:
            var inOrder = genre.value.songs.sorted { $0.played < $1.played }
            
            let last = inOrder.popLast()
            let secondLast = inOrder.popLast()
            
            if last?.played == secondLast?.played && last!.index > secondLast!.index {
                result.append((secondLast?.index)!)
                result.append((last?.index)!)
            } else {
                result.append((last?.index)!)
                result.append((secondLast?.index)!)
            }

        default: print("error")
        }
    }

    return result
}

그래서?

잘 됐을까요?

예압

근데 말이죠

코드가 좀 지저분하기도 하고, 가장 큰 두 녀석을 뽑을 때 .sorted을 쓰기는 시간복잡도가 O(n log n)이라 아무래도 좀 마음이 불편하단 말이죠.

그러니 두 가지를 목표로 코드를 수정해봅시다.

  1. 지저분한 코드 깔끔하게 변경하기
  2. .sorted 대신 다른 방법으로 가장 재생횟수가 높은 두 곡 뽑기

1. 지저분한 코드 깔끔하게 변경하기

지저분한 코드에 가장 큰 지분을 차지하는 반복문을 가지고 왔습니다.

for genre in sortedByTotalPlays {
    
    switch genre.value.songs.count {
    case 1: result.append(genre.value.songs[0].index)
    case 2:
        let first = genre.value.songs[0]
        let second = genre.value.songs[1]
        
        if first.played > second.played {
            result.append(first.index)
            result.append(second.index)
        } else if first.played < second.played {
            result.append(second.index)
            result.append(first.index)
        } else if first.index < second.index {
            result.append(first.index)
            result.append(second.index)
        } else if first.index > second.index {
            result.append(second.index)
            result.append(first.index)
        }
    case 3...:
        var inOrder = genre.value.songs.sorted { $0.played < $1.played }
        
        let last = inOrder.popLast()
        let secondLast = inOrder.popLast()
        
        if last?.played == secondLast?.played && last!.index > secondLast!.index {
            result.append((secondLast?.index)!)
            result.append((last?.index)!)
        } else {
            result.append((last?.index)!)
            result.append((secondLast?.index)!)
        }
        
    default: print("error")
    }

으...

눈쌀이 찌푸려지는군요

밑에 2번에서 만들 getTwoMaxValues 메서드로 대체해줍니다.

for genre in sortedByTotalPlays {
    
    if genre.value.songs.count == 1 {
        result.append(genre.value.songs[0].index!)
    } else if genre.value.songs.count >= 2 {
        result.append(contentsOf: genre.value.getTwoMaxValues())
    }
}

한결 낫네요.

2. .sorted 대신 다른 방법으로 가장 재생횟수가 높은 두 곡 뽑기

GenreDetail 구조체 내부에 새로운 메서드를 선언해줍니다.

가장 많은 플레이 수를 기록한 2곡을, 그리고 플레이수가 가장 많은 곡이 동일하면 인덱스가 적은 친구를 반환하도록 해줍니다.

func getTwoMaxValues() -> [Int] {
    var first = Song()
    var second = Song()
    
   // 반복문을 한번만 거치기에 시간복잡도가 O(n)이 됩니다.
    for song in songs {
        if song.played > first.played {
            second = first
            first = song
        } else if song.played > second.played {
            second = song
        }
    }
    
    if first.played == second.played && first.index! > second.index! {
        return [second.index!, first.index!]
    } else {
        return [first.index!, second.index!]
    }
}

옵셔널 강제 추출을 좋아하진 않지만, 추후 호출이 될 때, Song이 두 개 이상 들어있는 Array에서만 호출을 하기 때문에 로직 상 안전할 것 같아서 강제 추출을 때려버렸습니다.

그래서...

최종 코드

import Foundation

typealias Genre = String

struct GenreDetails {
    private(set) var songs: [Song] = []
    private(set) var totalPlays: Int = 0
    
    mutating func addSong(_ song: Song) {
        songs.append(song)
        totalPlays += song.played
    }
    
    func getTwoMaxValues() -> [Int] {
        var first = Song()
        var second = Song()
        
        for song in songs {
            if song.played > first.played {
                second = first
                first = song
            } else if song.played > second.played {
                second = song
            }
        }
        
        if first.played == second.played && first.index! > second.index! {
            return [second.index!, first.index!]
        } else {
            return [first.index!, second.index!]
        }
    }
}

struct Song {
    let played: Int
    let index: Int?
    
    init() {
        self.played = 0
        self.index = nil
    }
    
    init(played: Int, index: Int?) {
        self.played = played
        self.index = index
    }
}

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var hashMap: [Genre: GenreDetails] = [:]
    var result: [Int] = []
    
    for index in 0..<genres.count {
        let song = Song(played: plays[index], index: index)
        hashMap[genres[index], default: GenreDetails()] .addSong(song)
    }
    
    let sortedByTotalPlays = hashMap.sorted { (first, second) in
        return first.value.totalPlays > second.value.totalPlays
    }
    
    for genre in sortedByTotalPlays {
        
        if genre.value.songs.count == 1 {
            result.append(genre.value.songs[0].index!)
        } else if genre.value.songs.count >= 2 {
            result.append(contentsOf: genre.value.getTwoMaxValues())
        }
    }

    return result
}

잘 되는군요.

근데 사실...

1.의 반복문에서

else if genre.value.songs.count >= 2 {
	result.append(contentsOf: genre.value.getTwoMaxValues())
}

요 부분은 count가 2일때 약간의 성능 상 손해보는 부분이 있긴 합니다.

getTwoMaxValues()메서드를 거칠 필요 없이 두 노래의 재생횟수를 비교하면 되는데, 메서드를 거침으로써 약간의 손해를 봐서 그렇습니다.

극한의 성능을 쥐어짜야한다면 저것까지도 고려하는 것이 좋겠습니다.

여튼 여기까지만 해야겠네요.

profile
김하민
이전 포스트

소수 만들기

다음 포스트

올바른 괄호

0개의 댓글