티스토리 뷰
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.
문제 분류는 '해시'. Key-Value 쌍으로 데이터를 저장하는 자료구조를 말한다. 파이썬에서 딕셔너리라고 하는 그것이다.
예를 들어서
genres: [classic, pop, classic, classic, pop]
plays: [500, 600, 150, 800, 2500]
이렇게 입력이 들어왔다면, 총합 재생수가 더 많은 장르는 pop이고 그 다음이 classic이므로 pop 장르 중 play 수가 많은 순으로 두 곡 -> classic 장르 중 play 수가 많은 순으로 두 곡 순서로 출력한다.
- 내 코드
문제를 풀기 위해 고려했던 점들을 정리하면 이렇다.
1) 일단 장르별 재생수를 알아야 어떤 장르의 곡들을 먼저 찾을지 정할 수 있다. 그러므로 장르별 재생수를 담기 위한 dict를 하나 만들고, genres랑 plays 배열을 돌면서 dict의 값을 업데이트한다.
2) 재생수가 많은 장르 순으로 보기 위해 dict를 value 기준으로 정렬한다.
* 파이썬에서 dict를 sort/sorted 함수에 넣으면 key를 기준으로 정렬을 한다. 그러니까 지금과 같은 경우엔 장르명의 알파벳 오름차순으로 정렬이 된다. value 기준으로 정렬하고 싶으면 sorted 함수의 'key' 인자를 이용해서 이를 지정해주면 되는데, 이 때 lambda 표현식을 주로 많이 사용한다.
res = sorted(genres_plays, key=(lambda x: genres_plays[x]), reverse = True)
sorted 함수의 정의에 따르면 key 인자에는 '함수' 가 들어가야 한다. 이 함수는 정렬할 대상을 한 레코드씩 받아서 입력값으로 쓰고 그에 대한 리턴값으로 정렬을 하게 된다.
파이썬에서 lambda란 이름이 없는 한줄짜리 함수다. 위의 경우 x를 매개변수로 받아서 genres_plays[x] (=value) 를 리턴한다는 뜻으로, key 인자로 이 함수를 넣었으므로 '장르-플레이수' 묶음이 하나씩 들어가면서 '플레이수' 기준으로 정렬이 될 것이다.
근데 그냥 저렇게 쓰면 sorted는 키를 사용한 리스트를 반환한다. 그러니까 res가 ['pop', 'classic'] 이렇게 나온다. 플레이수까지 살리고 싶다면? dict의 items() 메서드를 사용해서 key, value를 다 가져온 다음, lambda 함수에서 value를 리턴해주면 된다.
res = sorted(genres_plays.items(), key=(lambda x: x[1]), reverse = True)
items() 메서드의 결과로 x[0] 은 key, x[1] 은 value가 된다.
3) 재생수가 많은 장르부터 하나씩 뽑아서, genres 배열을 다시 돌면서 해당 장르를 찾는다. 해당 장르라고 해서 다 베스트앨범에 들어가는게 아니라 재생수 TOP 2만 들어가야 하므로, 재생수 No. 1과 No. 2에 해당하는 index와 그 재생수 값을 저장하기 위한 변수를 만들어서 해당 장르를 찾을 때마다 비교하면서 업데이트한다.
4) 베스트앨범에 들어갈 곡 번호를 담을 배열 (answer) 에 재생수 No. 1, No. 2에 해당하는 index를 넣고 다음 장르로 넘어가서 반복한다. 단 해당 장르의 곡이 하나뿐이면 하나만 넣어야 하므로 if문을 써서 처리를 해준다.
def solution(genres, plays):
answer = [];
genres_plays = {};
for i in range(len(plays)): # 1) 장르별 재생수를 얻는 부분
g = genres[i];
p = plays[i];
if g not in genres_plays:
genres_plays[g] = p; # 키가 없으면 새로 추가해주고
else:
genres_plays[g] += p; # 키가 이미 있으면 값만 업데이트한다.
# 2) dictionary를 정렬하는 방법. lambda 함수를 사용했다.
res = sorted(genres_plays.items(), key=(lambda x: x[1]), reverse = True)
# 3) 장르별 No. 1, No. 2를 찾는 부분
for i in range(len(res)): # 장르: res[i][0]
first_play = 0;
second_play = 0;
first_play_index = -1;
second_play_index = -1;
for j in range(len(plays)):
if genres[j] == res[i][0]: # 장르가 일치하면,
if plays[j] > first_play: # 재생수가 현재 No. 1보다 높은지 비교
second_play = first_play; # 현재 No. 1이 No. 2로 밀려난다
second_play_index = first_play_index;
first_play = plays[j];
first_play_index = j;
elif plays[j] > second_play: # No. 1보단 낮다면, No. 2보단 높은지 비교
second_play = plays[j];
second_play_index = j;
if first_play_index != -1: # 4) 곡 번호를 넣는 부분
answer.append(first_play_index);
if second_play_index != -1: # 곡이 하나뿐이라 이걸 못찾은 경우 -1일 것
answer.append(second_play_index);
return answer처음에는 No. 1이 갱신될 때 No. 1을 No. 2로 밀어내는 코드를 넣지 않아서 틀렸는데 그걸 수정해줬더니 바로 정답이 나왔다. 레벨 3치고는 무난하게 풀 수 있었던 문제였다.
- 다른 사람의 코드
다른 사람들 코드를 몇 개 보고 많은 공부를 했다...
> 'from collections import defaultdict' 를 하고 defaultdict() 라는 메서드를 쓰면 dict 키의 기본값을 지정해서 키가 이미 없더라도 에러를 발생시키지 않고 기본값을 사용하게 할 수 있다. 예를 들어 defaultdict(int) 나 defaultdict(lambda: 0) 으로 만들어주면 키가 없으면 0을 넣는다. 이걸 사용하면 위 코드에서 '키가 없는지 체크하고 없으면 새로 추가해주는' 부분을 빼도 되기에 코드가 더 간결해진다.
> 내장 함수 zip(). 리스트 등 2개 이상의 iterable한 자료형이 있을 때, 둘의 크기가 같다면 짝지어서 쓸 수 있다. 아래와 같이 해주면 range 함수로 for문을 만들고 안에서 genres[i], plays[i] 를 뽑아내는 과정을 한줄로 줄일 수 있다.
for genre, play in zip(genres, plays):
...
> 짜면서 대충 느낌은 왔지만 3) 파트가 너무 쓸데없이 길다. 보통 max값을 찾는다고 하면 파이썬에선 그냥 max() 함수같은걸 쓰지 for문을 돌면서 비교를 하는 코드를 직접 넣진 않는다는 점을 생각해보자. max값 하나가 아니라 No. 1이랑 No. 2 두개를 찾아야해서 저렇게 짰다곤 하지만... 그걸 찾기 위해서 변수를 4개나 쓴게 뭔가 찝찝하다. 비유하자면 배열이라는 개념을 잘 모르는 프로그래밍 생초보가 int a1, a2, a3, a4 이렇게 변수를 선언해놓은걸 보는 느낌이다.
다른 사람들의 풀이를 보니 대체로 장르별로 어떤 곡들이 속해있는지를 정의해놓은 dict를 하나 더 만들어서 풀었더라. 그러면 장르별로 곡들이 묶여있으니까 그 안에서 sorted() 함수를 써버린 다음 제일 앞의 두개를 뽑아오면 되는 것이다.
이와 같은 개선점들을 적용해서 다시 짠 코드는 아래와 같다.
from collections import defaultdict
def solution(genres, plays):
answer = [];
genres_plays = defaultdict(int);
genres_songs = defaultdict(lambda: [])
i = 0;
for g, p in zip(genres, plays):
genres_plays[g] += p;
genres_songs[g].append((i, p))
i += 1;
sorted_genres = sorted(genres_plays.items(), key=(lambda x: x[1]), reverse = True)
for g in sorted_genres:
sorted_g = sorted(genres_songs[g[0]], key=(lambda x: x[1]), reverse=True)
answer.append(sorted_g[0][0])
if len(sorted_g) > 1:
answer.append(sorted_g[1][0])
return answer수정 전 코드와 수정 후 코드를 각각 돌려봤는데 시간 차이는 의외로 별로 나지 않았다. 대신 코드 라인수가 37줄에서 22줄로 크게 줄었다. 일반적으로 라인수 (LOC) 가 적은 코드일수록 유지보수성이 좋다고 평가하는 것을 생각해보면 코드를 간결하게 짜는 방법을 익혀두는 것은 분명 의미가 있다.