[알고리즘/Swift] 해시 - 베스트앨범

Swift 스터디 11주차 - 해시 :: 위장, 베스트앨범

[알고리즘/Swift] 프로그래머스 - 위장 (해시)

프로그래머스 해시 - 베스트앨범

👀 첫번째 풀이

# 딕셔너리 형태

• playDict 는 ["장르" : (총 재생곡수, [재생곡수])] 형태의 딕셔너리이다.
• 같은 장르의 총 재생곡수에 따라 1차 정렬을 해줘야하기 때문에, 총 재생곡수를 추가적으로 저장했다.
• musicDict 는 ["장르_재생곡수" : [고유번호]] 형태의 딕셔너리이다.
• 같은 장르에 같은 재생곡수를 가진 노래가 여러개 있을 수 있기 때문에, 고유번호를 배열로 저장했다.

playDict = {
  "장르1" : {
    총 재생 수 : 1300,
    재생 수 : [500, 500, 300]
  },
  "장르2" : { ... }
}

musicDict = {
  "장르1_500" : [0, 1],
  "장르1_300" : [2],
  ...
}

 

# 베스트 앨범을 모을때에는 다음 순서로 동작한다.

1. playDict 의 요소들을 총 재생곡수에 따라 내림차순으로 정렬한다.
2. playDict 의 각 요소의 [재생곡수] 를 내림차순으로 정렬한다.
3. 위 과정을 통해 musicDict 의 키값인 "장르_재생곡수" 형태로 만든 후, [고유 번호]를 오름차순으로 정렬한다.
4. 2-3번을 반복하며 각 장르마다 최대 2개의 노래를 베스트 앨범에 추가한다.

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var playDict = [String: (total: Int, each: [Int])]()
    var musicDict = [String: [Int]]()

    for i in 0..<genres.count {
        if playDict.keys.contains(genres[i]) {
            playDict[genres[i]]!.total += plays[i]
            playDict[genres[i]]!.each.append(plays[i])
        } else {
            playDict[genres[i]] = (total: plays[i], each: [plays[i]])
        }

        let key = genres[i] + String(plays[i])
        if musicDict.keys.contains(key) {
            musicDict[key]!.append(i)
        } else {
            musicDict[key] = [i]
        }
    }

    var bestMusics = [Int]()
    for (k, value) in playDict.sorted(by: { $0.value.total > $1.value.total }) {
        var count = 0
        for play in value.each.sorted(by: >) {
            let key = k + String(play)
            for music in musicDict[key]!.sorted() {
                guard count < 2 else { break }
                bestMusics.append(music)
                count += 1
            }
        }
    }

    return bestMusics
}

 

🤔 두번째 풀이

• 첫번째 풀이에서 playDict, musicDict 두 개의 딕셔너리를 쓰는 것을 하나로 합치면 좋겠다 싶어, 고민해봤다. 
• JSON 데이터를 받을때처럼 딕셔너리 안에 딕셔너리 형태로 고려했다. (아래 참고.. 좀 틀렸을 수도 있다) 
• 그치만 2중 딕셔너리로 구현하려니 요소 접근 방법이 너무 복잡하고, 첫번째 풀이보다 시간이 좀 더 걸렸다.

 

# 딕셔너리 형태

• 먼저, Play 는 각 장르마다 필요한 값들을 저장하는 (총 재생수, [재생수: [고유번호]]) 형태의 튜플이다.
• musics 는 [장르: Play] 형태의 딕셔너리이다.  
• 한번에 확인해보면 musics 는 [장르:(총 재생수, [재생수: [고유번호]])] 인 것이다.

musics = { 
  "장르1" : 
    {
      "총 재생수" : 1300
      "각 재생수" : [
        { 300 : [0] }, 
        { 500 : [1, 2] }
      ]
    }
  "장르2" : { ... }
}

 

# 베스트 앨범을 모을때에는 다음 순서로 동작한다.

1. musics 딕셔너리를 전체 재생 수에 따라 내림차순 정렬한다.
2. musics 딕셔너리 요소의 value 인 (total: 전체재생수, each: [재생 수: [고유번호]]) 이다.
3. value.each 인 [재생 수: [고유번호]] 를 재생 수에 따라 내림차순 정렬한다.
4. [고유번호] 를 오름차순 정렬해서, bestMusics 배열에 최대 2개만큼 넣어준다. 

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    // [장르: (전체재생수, [재생수:[고유번호]])]
    typealias Play = (total: Int, ids: [Int:[Int]])
    var musics = [String:Play]()

    for i in 0..<genres.count {
        let key = genres[i], play = plays[i]
        if musics.keys.contains(key) {
            musics[key]!.total += play
            if musics[key]!.ids.keys.contains(play) {
                musics[key]!.ids[play]!.append(i)
            } else {
                musics[key]!.ids[play] = [i]
            }
        } else {
            musics[key] = Play(total: play, ids: [play: [i]])
        }
    }

    var bestMusics = [Int]()
    for (_, value) in musics.sorted(by: { $0.value.total > $1.value.total }) {
        var count = 0
        for (_, ids) in value.ids.sorted(by: {$0.key > $1.key}) {
            for id in ids {
                guard count < 2 else { break }
                bestMusics.append(id)
                count += 1
            }
        }
    }

    return bestMusics
}

---

Review :: 엄청난 시간차이가 나는 건 아니지만, 풀이1과 풀이2중에 어떤게 더 보기좋은 풀이인지 구분하기가 어렵다.. 

첫번째 풀이 vs 두번째 풀이