베스트앨범

🔒 문제

🧠 생각의 흐름

1. 장르간 대결
   key: 장르별 노래 플레이 총합수
   value : (index번호, play수) // struct 정의가 필요하겠구만
   위 테스트 케이스를 예를 들어보면

   3100: [{1 600} {4 2500}]
   1450: [{0 500} {2 150} {3 800}]

2. 장르 내에서 2위까지만
   2위까지만 한다는 것은 Heap 정렬시 할때 최상위 2개만 필요함. 원소 갯수가 1개면 그대로 리턴

🔑 풀이 (Go)

package main

import (
	"fmt"
	"sort"
)

// An IntHeap is a min-heap of ints.

type song struct {
	index     int
	playCount int
}

type GenrePlayNumberList []song

func (songs GenrePlayNumberList) Len() int { return len(songs) }
func (songs GenrePlayNumberList) Swap(i, j int) {
	songs[i], songs[j] = songs[j], songs[i]
}
// Less  < : 이전 것이 작으면 안바꿈 > 이전 것이 크거나 같으면 안바꿈
// > 는 내림차순
func (songs GenrePlayNumberList) Less(i, j int) bool {
	return songs[i].playCount > songs[j].playCount
}



func solution(genres []string, plays []int) []int {

	var answer []int

	// Generate genres playCount
	// ex) pop: N, classic: M
	// make elements totalPlayCounts GenreName: genre name, value: The number of genre

	genreTable := make(map[string][]song)
	// order by count of play song
	orderTable := make(map[int][]song)

	for index, genre := range genres {
		genreTable[genre] = append(genreTable[genre], song{index,  plays[index]})
	}

	for _, songs := range genreTable {
		totalPlayCountOfSong := 0
		for _, song := range songs {
			totalPlayCountOfSong += song.playCount
		}
		orderTable[totalPlayCountOfSong] = songs
	}

	var totalPlayCounts []int

	for count := range orderTable {
		totalPlayCounts = append(totalPlayCounts, count)
	}

	// order by descending of total play count
	sort.Sort(sort.Reverse(sort.IntSlice(totalPlayCounts)))


	for _, count := range totalPlayCounts {
		playList := make(GenrePlayNumberList, 0)

		for _, song := range orderTable[count] {
			playList = append(playList, song)
		}

		sort.Stable(playList)

		for i := 0; i < 2; i++ {
			answer = append(answer, playList[i].index)
			if len(playList) == 1 {
				break
			}
		}
		
	}


	fmt.Println(answer)
	return answer
}

😯 실수

• 문제를 잘못 읽어서 "장르별 토탈 플레이수" 가 아니라 "장르별 노래 수" 로 풀었다.

• "모든 장르는 재생 횟수가 다릅니다"를 각 노래별로 재생횟수도 다른 것으로 생각했다. 사실은 장르별 수록곡의 재생 총합이 서로 다르다는 것이었다.