베스트앨범

베스트앨범
해시 
6524명 완료

https://programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

 

파이썬(python)

딕셔너리를 잘 이용하면 쉽게 풀 수 있는 문제입니다. 
(집계할 때 딕셔너리를 쓰면 편한 경우가 많습니다.)

딕셔너리에 초기값을 설정하는 것은 꽤 귀찮은 일입니다. 
이럴 때 defaultdict를 사용할 수 있습니다.

from collections import defaultdict


def solution(genres, plays):
    answer = []
    genre_plays, song_plays = defaultdict(int), defaultdict(list)
    for index, (play, genre) in enumerate(zip(plays, genres)):
        genre_plays[genre] += play
        song_plays[genre].append((play, index))
    for genre, _ in sorted(genre_plays.items(), key=lambda x: -x[1]):
        for _, index in sorted(song_plays[genre], key=lambda x: (-x[0], x[1]))[:2]:
            answer.append(index)
    return answer

하지만 굳이 defaultdict를 쓰지 않고 get, setdefault를 응용해도 됩니다. 

def solution(genres, plays):
    answer = []
    genre_plays, song_plays = {}, {}
    for index, (play, genre) in enumerate(zip(plays, genres)):
        genre_plays[genre] = genre_plays.get(genre, 0) + play
        song_plays.setdefault(genre, []).append((play, index))
    for genre, _ in sorted(genre_plays.items(), key=lambda x: -x[1]):
        for _, index in sorted(song_plays[genre], key=lambda x: (-x[0], x[1]))[:2]:
            answer.append(index)
    return answer

마지막 부분을 리스트 컴프리헨션을 이용해 수정해 보았습니다. 
리스트 컴프리헨션에 이중 for문을 사용하는 것은 가독성에 문제가 있으므로 추천되지 않습니다. 

def solution(genres, plays):
    genre_plays, song_plays = {}, {}
    for index, (play, genre) in enumerate(zip(plays, genres)):
        genre_plays[genre] = genre_plays.get(genre, 0) + play
        song_plays.setdefault(genre, []).append((play, index))
    return [index for genre, _ in sorted(genre_plays.items(), key=lambda x: -x[1])
            for _, index in sorted(song_plays[genre], key=lambda x: (-x[0], x[1]))[:2]]

고(go)

func solution(genres []string, plays []int) (answer []int) {
	genre_plays := make(map[interface{}]int)
	song_plays := make(map[string]map[interface{}]int)
	for i, genre := range genres {
		genre_plays[genre] += plays[i]
		if _, ok := song_plays[genre]; !ok {
			song_plays[genre] = make(map[interface{}]int)
		}
		song_plays[genre][i] = plays[i]
	}
	for len(genre_plays) > 0 {
		g_max := max(genre_plays).(string)
		repeat := 0
		if len(song_plays[g_max]) == 1 {
			repeat = 1
		} else {
			repeat = 2
		}
		for i := 0; i < repeat; i++ {
			s_max := max(song_plays[g_max]).(int)
			answer = append(answer, s_max)
			delete(song_plays[g_max], s_max)
		}
		delete(genre_plays, g_max)
	}
	return
}

func max(plays map[interface{}]int) (max_k interface{}) {
	var max_v int
	for k, v := range plays {
		if v > max_v {
			max_k, max_v = k, v
		}
	}
	return
}

테스트 1 〉	통과 (0.00ms, 3.94MB)
테스트 2 〉	통과 (0.00ms, 3.93MB)
테스트 3 〉	통과 (0.00ms, 3.95MB)
테스트 4 〉	통과 (0.00ms, 3.9MB)
테스트 5 〉	통과 (0.04ms, 3.93MB)
테스트 6 〉	통과 (0.04ms, 3.7MB)
테스트 7 〉	통과 (0.02ms, 3.94MB)
테스트 8 〉	통과 (0.01ms, 3.93MB)
테스트 9 〉	통과 (0.01ms, 3.93MB)
테스트 10 〉	통과 (0.04ms, 3.93MB)
테스트 11 〉	통과 (0.01ms, 3.91MB)
테스트 12 〉	통과 (0.03ms, 3.94MB)
테스트 13 〉	통과 (0.05ms, 3.93MB)
테스트 14 〉	통과 (0.05ms, 3.94MB)
테스트 15 〉	통과 (0.00ms, 3.94MB)

구조체를 만드는 건 흔하니까,
'인터페이스 타입(empty interface, interface type)'을 사용해 보았습니다.
좋은 판단은 아니었던 것 같고 ^^; '인터페이스 타입'을 처음으로 써본 거라 공부는 된 것 같습니다. 

인터페이스 타입을 사용하면, 타입 어서~ㄹ션(Type Assertion)도 같이 쓰게 됩니다.
'변수.(타입)'의 형식입니다. 

Assertion은 표명, 가정의 뜻이 있습니다. 여기선 표명의 뜻으로 쓰인 것 같습니다. 

 

import "sort"

type Song struct {
	id, played int
}

type Genres struct {
	played int
	songs  []Song
}

func solution(genres []string, plays []int) (answer []int) {
	genresMap := make(map[string]Genres)
	for i, genre := range genres {
		genresMap[genre] = Genres{genresMap[genre].played + plays[i],
			append(genresMap[genre].songs, Song{i, plays[i]})}
	}
	var list []Genres
	for _, v := range genresMap {
		list = append(list, v)
	}
	sort.Slice(list, func(i, j int) bool {
		return list[i].played > list[j].played
	})
	for _, each := range list {
		sort.Slice(each.songs, func(x, y int) bool {
			if each.songs[x].played == each.songs[y].played {
				return each.songs[x].id < each.songs[y].id
			}
			return each.songs[x].played > each.songs[y].played
		})
		for i, song := range each.songs {
			if i > 1 {
				break
			}
			answer = append(answer, song.id)
		}
	}
	return
}

테스트 1 〉	통과 (0.01ms, 3.9MB)
테스트 2 〉	통과 (0.01ms, 3.93MB)
테스트 3 〉	통과 (0.01ms, 3.82MB)
테스트 4 〉	통과 (0.00ms, 3.92MB)
테스트 5 〉	통과 (0.03ms, 3.92MB)
테스트 6 〉	통과 (0.02ms, 3.66MB)
테스트 7 〉	통과 (0.01ms, 3.93MB)
테스트 8 〉	통과 (0.01ms, 3.93MB)
테스트 9 〉	통과 (0.01ms, 3.92MB)
테스트 10 〉	통과 (0.03ms, 3.92MB)
테스트 11 〉	통과 (0.01ms, 3.93MB)
테스트 12 〉	통과 (0.02ms, 3.93MB)
테스트 13 〉	통과 (0.03ms, 3.93MB)
테스트 14 〉	통과 (0.03ms, 3.93MB)
테스트 15 〉	통과 (0.01ms, 3.92MB)