문제
https://school.programmers.co.kr/learn/courses/30/lessons/42579
문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.
입출력 예
genres plays return
["classic", "pop", "classic", "classic", "pop"][500, 600, 150, 800, 2500] [4, 1, 3, 0]
입출력 예 설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
고유 번호 3: 800회 재생
고유 번호 0: 500회 재생
고유 번호 2: 150회 재생
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
고유 번호 4: 2,500회 재생
고유 번호 1: 600회 재생
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.
장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.
※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.
접근
1차 접근 : {장르 : [ {고유번호:재생횟수},{고유번호:재생횟수} ,,, ]}
결과 : 테스트4, 테스트15 제외 "런타임에러"
아래와 같이 접근하였다.
{장르 : 전체횟수}구한 뒤, "전체횟수" 기준 "내림차순" 정렬{장르 : [ {고유번호:재생횟수},{고유번호:재생횟수} ,,, ]}구하기"재생횟수"기준"내림차순"으로 고유번호 정렬전체횟수 내림차순으로 순회,
모든 장르 중 고유번호 최소갯수만큼 고유번호 추출,
result 리스트에 append
사실 이 풀이에는 함정이 있다. 무엇일까?
def solution(genres, plays):
answer = []
#1
allPlays = dict()
for g,p in zip(genres,plays):
allPlays[g]=allPlays.get(g,0) + p
sortedAllPlays = dict(sorted(allPlays.items(),key=lambda x:x[1],reverse=True))
#2
playPerGenres = dict()
for idx,g in enumerate(genres):
play = {idx:plays[idx]}
if not (g in playPerGenres):
playPerGenres[g] = []
playPerGenres[g].append(play)
#3
sorted_playPerGenres = {genre: sorted(genre_data, key=lambda x: list(x.values())[0], reverse=True) for genre, genre_data in playPerGenres.items()}
#4
for sap in sortedAllPlays :
for i in range(0,len(sorted_playPerGenres)):
answer.append(list(sorted_playPerGenres[sap][i].keys())[0])
return answer사실 해당 풀이에서의 중요하게 놓친 포인트는 "왜 최대 두 개까지 모아 베스트 앨범을 출시하는가?" 이다.
그러나 정말 웃기게도, 최대 두 개를 모으는 정책은 베스트 앨범 출시 정책 조건이다.
문제는 테스트 조건케이스에는 적혀있지 않다는 것이다.
입출력 예 설명 섹션에 적혀있었다.
입출력 예 설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
,,,,
장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.
※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.
아니,,,;;;
이러면 누가 알겠냐고,,,
놓친 포인트를 개선하는 식으로 다음과 같이 코드를 리팩토링하였다.
1차 개선 : 최종선택 시, "장르 별 최대 2곡 선택"으로 리팩토링
결과 : 통과
로직은 동일하다.
다만 #1 이 수정되고, #5 가 추가되었다.
{장르 : 전체횟수}구한다.
"전체횟수" 기준 "내림차순" 정렬을 제거하였다.{장르 : [ {고유번호:재생횟수},{고유번호:재생횟수} ,,, ]}구하기- "재생횟수" 기준 "내림차순"으로 playPerGenres 정렬
- "총 재생횟수" 기준 "내림차순" 으로 total_plays_per_genre 정렬
- 장르 별 최대 2곡을 result 리스트에 추가
def solution(genres, plays):
answer = []
#1 {장르 : 전체횟수}
total_plays_per_genre = dict()
for g,p in zip(genres,plays):
total_plays_per_genre[g]=total_plays_per_genre.get(g,0) + p
#2 {장르 : [ {고유번호:재생횟수},{고유번호:재생횟수} ,,, ]}
playPerGenres = dict()
for idx,g in enumerate(genres):
play = {idx:plays[idx]}
if not (g in playPerGenres):
playPerGenres[g] = []
playPerGenres[g].append(play)
#3 "재생횟수" 기준 "내림차순"으로 playPerGenres 정렬
sorted_playPerGenres = {genre: sorted(genre_data, key=lambda x: list(x.values())[0], reverse=True) for genre, genre_data in playPerGenres.items()}
#4 "총 재생횟수" 기준 "내림차순" 으로 total_plays_per_genre 정렬
sorted_genres = sorted(total_plays_per_genre.keys(), key=lambda x: -total_plays_per_genre[x])
#5 장르 별 최대 2 노래 추가
for genre in sorted_genres:
count = 0
for pg in sorted_playPerGenres[genre]:
for idx,play in pg.items():
answer.append(idx)
count+=1
if count >= 2:
break
return answer타인의 접근 : 조건 별 자료구조 만들기
수많은 다른 풀이도 있었지만, "진짜 코딩테스트라면 이렇게 접근했을 것 같다" 라는 접근을 소개한다.
-
[장르, 재생횟수, 인덱스(고유번호)]를 형식으로 하는 리스트 생성
-
조건1. "속한 노래가 가장 많이 재생된 장르를 먼저 수록"을 만족시키기 위해서, 장르를 KEY로 하는 딕셔너리를 생성하여 VALUE에 KEY와 매칭되는 재생횟수를 저장
-
조건2.3. "재생 횟수가 많을수록, 같다면 고유번호가 낮을수록 먼저 수록"을 만족시키기 위해서, 1에서 생성한 리스트를 재생횟수 기준 내림차순, 고유번호 기준 오름차순 정렬
-
2에서 생성한 딕셔너리 KEY 순서대로 정렬한 리스트를 탐색하며 최대 count 2까지의 고유번호를 수록
def solution(genres, plays):
answer = []
temp = []
total_genre_d = {}
temp = [[genres[i], plays[i], i] for i in range(len(genres))] # [장르, 재생횟수, 고유 번호] 리스트
temp = sorted(temp, key=lambda x: (x[0], -x[1], x[2])) # 많이 재생될수록, 같다면 고유번호가 낮을수록
for g in temp: # {장르 : 총 재생횟수} 딕셔너리 생성
if g[0] not in total_genre_d:
total_genre_d[g[0]] = g[1]
else:
total_genre_d[g[0]] += g[1]
total_genre_d = sorted(total_genre_d.items(), key = lambda x: -x[1]) # 재생횟수가 많은 순서로 장르 정렬
for i in total_genre_d: # 같은 장르 내에서는 최대 2곡까지 조건대로 수록
count = 0
for j in temp:
if i[0] == j[0]:
count += 1
if count > 2:
break
else:
answer.append(j[2])
return answer위 접근법은 내 기존풀이와 크게 다를 바 없지만, 자료구조를 최대한 최소화하여 활용했다는 점이 인상깊었다.
새로 배운 Python 문법
tuple 과 list 의 차이
dictionary 에서 key,value 에 접근하는 법
lambda 와 - 연산자 를 이용한 오름차순, 내림차순
# [장르, 재생횟수, 고유 번호]
temp = [['classic', 500, 0], ['pop', 600, 1], ['classic', 150, 2], ['classic', 800, 3], ['pop', 2500, 4]]
# 1) [장르, 재생횟수, 고유번호] 각각 순서대로 오름차순 정렬
temp = sorted(temp, key=lambda x : (x[0],x[1],x[2]))
# 2) 재생횟수 내림차순 정렬
temp = sorted(temp, key=lambda x : -x[1])
# 3) [장르, 재생횟수, 고유번호]에 대해 장르 오름차순, 재생횟수 내림차순, 고유번호 오름차순
temp = sorted(temp, key=lambda x : (x[0],-x[1],x[2]))
"""
1)
[['classic', 150, 2], ['classic', 500, 0], ['classic', 800, 3], ['pop', 600, 1], ['pop', 2500, 4]]
"""
"""
2)
[['pop', 2500, 4], ['classic', 800, 3], ['pop', 600, 1], ['classic', 500, 0], ['classic', 150, 2]]
"""
"""
3)
[['classic', 800, 3], ['classic', 500, 0], ['classic', 150, 2], ['pop', 2500, 4], ['pop', 600, 1]]
"""List Comprehension
[ ( 변수를 활용한 값 ) for ( 사용할 변수 이름 ) in ( 순회할 수 있는 값 )]sorted_genres = sorted(total_plays_per_genre.keys(), key=lambda x: -total_plays_per_genre[x])https://shoark7.github.io/programming/python/about-list-comprehension-python
