[프로그래머스/Python] 알고리즘고득점Kit-해시-베스트앨범

📌 문제 링크

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

프로그래머스

 

 

📌 문제 설명

사용한 테스트 케이스 참고: 

 

 

📌 풀이 과정 

🍀 1번째 시도: Runtime Error 

• hash map (k, v) => 2개를 만들기로 했다. 
  • gp_hmap: k = 장르 v  = 장르별 plays값 누적 더함 
  • gi_hmap: k = 장르 v = 장르별 인덱스 모음
• gp_hmap은 정렬을 진행했다. 
  • 이유: "1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다." 해당 기준을 만족시키고자 했다.
  • sorted_gpHmap = sort(gp_hmap.items(), key=lambda x:x[1], reverse=True)
    1. items()가 리스트 형태로 각 요소 [k,v] 를 리턴
    2. lambda 식에 의해 v값을 기준으로 내림차순 정렬을 한다.
• sorted_gpHmap의 key값인 k에 대해서 
  • gi_hmap.items() = [ki, vi] 각각을 돌린다. (ki = 장르 vi = 해당 장르에 속하는 노래 고유번호 리스트) 
  • k == ki 가 True이면 (장르가 일치하면)
    • for i in vi : 해당 장르의 노래 고유번호 리스틀 돌려 tmp에 (i, plays[i])를 추가한다. 
    • 다 추가하면 tmp 를 plays[i] 값 기준으로 내림차순 sort 하여 앞에서 2개씩 i 만 뽑아 answer에 추가한다. 
  • 즉, 각 k값에 대해 이를 반복하게 되면 tmp에는 장르마다 plays[i] 값 기준으로 노래 고유번호를 담는다! 

def solution(genres, plays):
    answer = []
    # 해시맵 2개 1. 장르: plays 2. 장르: 인덱스 
    gp_hmap = {} # 장르: plays
    gi_hmap = {} # 장르: 인덱스 
    
    for i in range(len(genres)):
        if genres[i] not in gp_hmap: 
            gp_hmap[genres[i]] = plays[i]
            gi_hmap[genres[i]] = [i]
        else: 
            gp_hmap[genres[i]] += plays[i]
            gi_hmap[genres[i]].append(i) 
    
    sorted_gpHmap = dict(sorted(gp_hmap.items(), key=lambda x:x[1], reverse=True))
    
    for k in sorted_gpHmap.keys():
        for ki, vi in gi_hmap.items():
            tmp = []
            if k == ki:
                for i in vi: 
                    tmp.append((i,plays[i]))
                tmp.sort(key=lambda x:x[1], reverse=True)
                # print(tmp)
                for i in range(2):
                    answer.append(tmp[i][0])
    return answer

 

=> 문제점) 

• 해시맵을 2개나 사용하고 있고 런타임에러가 발생하는 걸로 보아 너무 비효율적이라는 점
• 그래서 해시맵 하나로 최대한 해결해보려고 했다. 어떤 조합으로 해시맵을 만들어야 하지 고민함. 

🍀 2번째 시도: PASS 

• 해시맵은 key = 장르, value = 해당 장르의 plays[i] 값 누적 으로만 사용하기로 했다. 그 뒤에 sort를 하면 재생 횟수 많은 장르를 고를 수 있게 된다. 
• 정렬된 해시맵의 각 장르 순서대로 plays에서 재생 횟수 높은 노래를 2개씩 고르면 된다고 생각했다. 
  • 따라서 tmp = []를 각 장르마다 새로 만들어줬다. 
  • 장르가 일치하면 그때의 i, plays[i]를 tmp에 추가해주고, plays[i] 값 기준으로 내림차순 정렬한다. 
  • 정렬된 tmp에 대해서 최대 2개만 담을 수 있다. (항상 2개 담는 게 아니다!!!) 
  • 그래서 cnt 변수를 따로 두고, for문으로 answer에 담았다. 
• ==> 풀이 코드는 아래에 !!

📌 풀이 코드 

def solution(genres, plays):
    answer = []
    # 1. 재생 횟수 많은 장르 고르기 
    hmap = {} 
    for i, g in enumerate(genres):
        if g in hmap.keys():
            hmap[g] += plays[i]
        else: 
            hmap[g] = plays[i]
    sort_hmap = dict(sorted(hmap.items(), key=lambda x:x[1], reverse=True))
    print(sort_hmap)
    # 2. 장르 안에서 많이 재생된 노래 고르기 
    for genre in sort_hmap.keys():
        tmp = []
        for i, v in enumerate(genres):
            if genre == v:
                tmp.append((i, plays[i]))
        tmp.sort(key=lambda x:x[1], reverse=True)
        cnt = 0
        for i, p in tmp: 
            answer.append(i)
            cnt += 1
            if cnt == 2:
                break 
    return answer