사용자 도구

사이트 도구


ps:problems:programmers:42579

베스트앨범

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42579
문제명베스트앨범
레벨Level 3
분류

구현

시간복잡도O(n+mlogm)
인풋사이즈m<=100, n<=10,000
사용한 언어Python
해결날짜2021/05/18
태그

고득점 Kit - 해시

풀이

  • 풀이 자체는 그냥 시키는 대로 구현하면 된다.
  • 그냥 이것저것 조건이 많아서 구현이 조금 지저분해지기 쉬운데, 어떻게 하면 좀 더 깔끔해질지를 생각할 여지는 있다
  • 시간 복잡도는 데이터를 전부 읽는데 O(n), 장르들을 정렬하는 데에, O(mlogm)이 필요하다. 장르마다 재생횟수가 많은 top2를 골라야 하는데 각각 정렬해서 찾으려고 하면 코드는 짧아지지만 O(nlogn)이 추가된다. 정렬하지 않고 그냥 리니어 서치로 top2를 찾으면 모든 장르에서 다 찾는데에 O(n)이니까 총 시간복잡도가 O(n+mlogm)

코드

"""Solution code for "Programmers 42579. 베스트앨범".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42579
- Solution link: http://www.teferi.net/ps/problems/programmers/42579
"""

import collections


def solution(genres, plays):
    songs_by_genre = collections.defaultdict(list)
    for song, genre in enumerate(genres):
        songs_by_genre[genre].append(song)
    answer = []
    for songs in sorted(songs_by_genre.values(),
                        key=lambda songs: -sum(plays[song] for song in songs)):
        answer.append(max(songs, key=lambda song: plays[song]))
        if len(songs) > 1:
            plays[answer[-1]] = -1
            answer.append(max(songs, key=lambda song: plays[song]))
    return answer

토론

댓글을 입력하세요:
F T F W D
 
ps/problems/programmers/42579.txt · 마지막으로 수정됨: 2021/05/22 17:38 저자 teferi