[프로그래머스] 베스트앨범[Level 3] (python 파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

def solution(genres, plays):
    d1 = {}
    d2 = {}
    s = {}
    
    for i in range(len(plays)):
        
        if genres[i] not in s:
            s[genres[i]] = plays[i]
        else:
            s[genres[i]] += plays[i]
            
            
        if genres[i] not in d1:
            d1[genres[i]] = [i, plays[i]]
            
        elif genres[i] not in d2:
            
            if plays[i] > d1[genres[i]][1]:
                d2[genres[i]] = d1[genres[i]]
                d1[genres[i]] = [i, plays[i]]
            else:
                d2[genres[i]] = [i, plays[i]]
                
            
        else:
            if plays[i] > d2[genres[i]][1]:

                if plays[i] > d1[genres[i]][1]:
                    d2[genres[i]] = d1[genres[i]]

                    d1[genres[i]] = [i,plays[i]]

                else:
                    d2[genres[i]] = [i,plays[i]]
              


    s = sorted(s.items(), key = lambda item: item[1], reverse = True)

    ans = []
    for i in s:
        
        ans.append(d1[i[0]][0])
        if i[0] in d2:
            ans.append(d2[i[0]][0])
    return ans

 

 

 

위 문제는 해시 문제이다.

 

 

프로그래머스의 알고리즘 고득점 Kit를 차근차근 풀어가다 푼 문제이다.

 

 

Kit에서 알 수 있듯이 위 문제는 Key-value 쌍을 잘 이용하여 푸는 문제이다

 

 

해시 = key-value

 

 

파이썬에서는 딕셔너리로 잘 구현되어있기 때문에 딕셔너리를 잘 구현하면 문제를 풀 수 있을 것이다.

 

문제 조건을 잘 보자.

 

 

---

문제조건 및 중요한 점

 

기존에도 말했듯이 코딩테스트를 풀 때 가장 중요한 것은 문제를 잘 읽고 이해하는 것이다.

 

위의 문제를 잘 이해해보자.

 

 

1. 노래의 장르와 노래 횟수가 주어진다.

2. 장르별 총 재생 횟수로 정렬한다.

3. 각 장르별 최대 2개의 노래까지 저장된다.

4. 같은 장르라면 재생 횟수가 큰 노래 먼저 정렬된다.

5. 같은 장르에 재상 횟수까지 같다면, 먼저 주어진 노래가 선택된다.

6. 장르의 노래가 하나면 하나면 저장된다.

 

 

주어진 문제를 보면 답의 구성이 대략 그려질 것이다.

 

가장 우선되는 기준은 장르별 총 재생 횟수이므로,

=> 장르별 총 재생 횟수가 필요하다. {"클래식" : 1000 , "팝 : 100", ... }

 

장르별 최대 2개의 노래가 저장되며, 재생 횟수의 순서로 저장된다. 

 

이때 저장되는 수는 노래의 인덱스 이다.

 

위의 조건에서 중요한 것은 2개 와 인덱스이다.

2개의 노래만 고려하므로, 그냥 장르별로 딕셔너리를 2개를 만들면 된다.

 

 

 

d1 = {}

d2 = {}

s = {}

 

s 에는 장르를 key로, 총 재생횟수를 value 로 넣어주고

 

d1,d2에는 각각 장르를 key로, [인덱스, 재생횟수] 를 value로 넣어준다.

 

이때 d1의 재생횟수를 항상 d2의 재생횟수보다 크게 하면, 위의 요구조건을 충족하게된다.

 

 

 

 

 

 

---

 

문제 해설

 

위에서

s 에는 장르를 key로, 총 재생횟수를 value 로 넣어주고

 

d1,d2에는 각각 장르를 key로, [인덱스, 재생횟수] 를 value로 넣어준다.

 

라고 설명했다.

 

즉

s의 역할 = 장르별 총 재생횟수를 저장하므로 첫 번째 정렬 조건을 위한 정보를 저장한다.

key를 장르로 정하면서, s의 key로 d1,d2를 접근할 수 있게 한다.

 

s를 별개의 딕셔너리를 지정함으로서 첫 번째 정렬 sort를 한 번만 수행해도 되는 장점이 존재한다.

 

d1,d2의 역할 = 딕셔너리를 2개로 함으로서 두 번째 정렬 조건을 위한 정보를 저장한다.

딕셔너리를 2개로 분리함으로서 정렬 sort 를 사용하지 않아도 되므로, 시간 복잡도가 줄어들게 된다.

 

 

 

해답의 진행 순서 

 

입력되는 genres와 plays를 for문으로 돈다.

 

 

 

if 현재 노래의 장르가 처음 입력되었다면?

 

=> d1에 노래 정보를 입력한다. 

 

 

 

 

if d1에는 있지만 d2에는 없다면?

 

=> d1의 노래 정보와 비교하여, d1, d2의 정보를 수정해준다.

 

=> 위 경우는 같은 장르의 노래가 두 번째로 입력된 경우이다.

 

예시로 2 번째 클래식 노래라고 한다면 d1과 비교하여, 첫 번째 클래식 노래의 횟수와 비교하여,

 

큰 노래는 d1, 작은 노래를 d2에 집어넣음으로서 d1이 d2보다 항상 커야 한다는 조건을 만족시킨다.

 

 

 

그 외의 경우

 

기존 두 경우 다음부터 오는 경우에서는 

현재 노래와 d1, d2의 재생횟수를 비교한 후, d1이 d2보다 항상 커야 하며,

d1, d2가 항상 장르별 첫 번째, 두 번째로 큰 노래임을 만족시키게 하면 된다.

 

 

 

for문을 모두 수행하면, s를 sort하면서 첫 번째 조건을 만족한다.

 

그 후, s를 순서대로 돌면서, d1,d2에서 노래의 인덱스를 뽑아 결과값에 순서대로 집어넣는다.

만약 d2에 값이 없으면, d1만 호출한다. 

 

 

 

 

 

---

정리

시간 복잡도를 줄이기 위해

1. 장르별 합계를 별개의 딕셔너리 s로 두어 만들었다. + key를 장르로 하여 d1,d2로 접근할 수 있는 인덱스를 만들었다.

2. d1,d2로 나누어 각각, 가장 큰 노래, 두번 째로 큰 노래로 정하여, sort()의 실행을 최소화 시켰다.

 

문제를 해결하기 위해

항상 d1이 d2보다 크게 하여, d1,d2의 조건을 만족시켰다.

 

문제 조건에서 

6. 장르의 노래가 하나면 하나면 저장된다.
는 노래가 하나인 경우도 입력된다는 것을 의미하므로,

답을 출력할 때, d2에 노래가 없는 경우도 고려해서 출력했다.