99클럽 코테 스터디 5일차 TIL, 프로그래머스 / 베스트앨범

🔑 오늘의 학습 키워드 : dictionary

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42579

 

from collections import defaultdict

def solution(genres, plays):
    answer = []
    streaming = defaultdict(int)
    each_played = defaultdict(list)
    
    # 장르별 플레이 횟수와 플레이 정보를 저장
    for idx,(genre,play) in enumerate(zip(genres,plays)):
        each_played[genre].append((idx,play))
        streaming[genre] += play
    
    # 장르별 총 플레이 횟수에 따른 정렬할 리스트
    chart = []
    for playtime in streaming:
        chart.append((streaming[playtime],playtime))
    chart.sort(reverse = True)
    
    # 가장 많이 들은 노래 찾기
    for gen in chart:
        # 장르에 노래가 하나밖에 없으면 해당 노래의 인덱스만 추가
        if len(each_played[gen[1]]) == 1:
            answer.append(each_played[gen[1]][0][0])
        else:
            each_played[gen[1]].sort(key = lambda x : (-x[1],x[0]))
            # 상위 2개의 노래 인덱스를 추가
            answer.append(each_played[gen[1]][0][0])
            answer.append(each_played[gen[1]][1][0])
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

알고리즘이 해시로 나와있었던 문제였다.

 

파이썬은 해시 자료구조가 딕셔너리(dictionary)로 되어있기 때문에 이를 활용해야겠다고 생각이 들었다.

 

그 후 자료구조를 잘 활용해서 상위 노래를 찾아야겠다고 생각을 했다.

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.

 

for문을 3번 돌았기 때문에 3N

✅ 알고리즘 개요

1. 장르별 플레이 횟수와 플레이 정보를 저장

# defaultdict
from collections import defaultdict

streaming = defaultdict(int)
each_played = defaultdict(list)

for idx,(genre,play) in enumerate(zip(genres,plays)):
    each_played[genre].append((idx,play))
    streaming[genre] += play

# dict
streaming = dict()
each_played = dict()

for idx,(genre,play) in enumerate(zip(genres,plays)):
	if genre in each_played and genre in streaming:
	    each_played[genre].append((idx,play))
    	streaming[genre] += play
    else :
    	each_played[genre] = [(idx,play)]
    	streaming[genre] = play

 

두 자료구조의 차이는 없는 key를 조회할때 발생하는데 

 

defaultdictionary는 초기값을 설정할 수 있어서 바로 연산이 가능해 가독성 및 코드가 짧아졌다.

 

성능은 둘이 비슷한 것으로 알고 있다.

 

2. 장르별 총 플레이 횟수에 따른 정렬을 위해 리스트 생성

- 정렬을 사용

 

3. 가장 많이 들은 노래 찾기

- 조건을 분기해서 정답에 추가

 

✅ 오늘의 회고

- 가독성이 좋은 코드란 관점에서 봤을 때 아직 많이 부족한 것 같다. (클린코드 저자가 보면 화낼것같다)

 

- 주석없이 이해가 가는 코드를 작성하기 위해 노력해야 할 것 같다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL