내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
베스트앨범
ps:problems:programmers:42579
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 베스트앨범 ====== ===== 풀이 ===== * 풀이 자체는 그냥 시키는 대로 구현하면 된다. * 그냥 이것저것 조건이 많아서 구현이 조금 지저분해지기 쉬운데, 어떻게 하면 좀 더 깔끔해질지를 생각할 여지는 있다 * 시간 복잡도는 데이터를 전부 읽는데 O(n), 장르들을 정렬하는 데에, O(mlogm)이 필요하다. 장르마다 재생횟수가 많은 top2를 골라야 하는데 각각 정렬해서 찾으려고 하면 코드는 짧아지지만 O(nlogn)이 추가된다. 정렬하지 않고 그냥 리니어 서치로 top2를 찾으면 모든 장르에서 다 찾는데에 O(n)이니까 총 시간복잡도가 O(n+mlogm) ===== 코드 ===== <dkpr py> """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 </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/42579.txt
· 마지막으로 수정됨: 2021/05/22 17:38 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로