본문 바로가기
Python/알고리즘문제

[프로그래머스][해시] 베스트앨범

by 붕어사랑 티스토리 2021. 3. 17.
반응형

programmers.co.kr/learn/courses/30/lessons/42579

 

코딩테스트 연습 - 베스트앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가

programmers.co.kr

이게 왜 해시문제이지... 전형적인 heap 문제인거 같은 느낌인데.... 일단 딕셔너리를 사용하긴 했다.

 

아이디어는 이렇다.

 

  • zip으로 장르와 플레이수를 합친 리스트를 만든뒤 dictionary 자료형으로 장르별 플레이수를 만든다.
  • 위에 나온 조건에 맞는 heap을 구현할 class를 생성한다.
  • heappop()을 하면서 dictionary 자료형으로 장르당 2번 나왔는지 체크한다

코드가 조금 난해한데 다른사람 코드도 보니 상당히 난해하다. 걍 그런 문제인가보다.

 

 

 

def solution(genres, plays):
    answer = []
    mylist = list(zip(genres,plays))
    print(mylist)
    plays_of_genre = {}
    
    for genre, play in mylist:
        if genre not in plays_of_genre:
            plays_of_genre[genre] = play
        else:
            plays_of_genre[genre] +=play
    print(plays_of_genre)
    import heapq
    hq = []
    length = len(mylist)
    for i in range(length):
            heapq.heappush(hq, song(plays_of_genre[genres[i]], plays[i],i))

    for i in hq:
        print(i)
    checkGenre = {}

    while hq:
        bestSong = heapq.heappop(hq)
        if bestSong.plays_of_genre not in checkGenre:
            checkGenre[bestSong.plays_of_genre] = 1
            answer.append(bestSong.number)
        elif checkGenre[bestSong.plays_of_genre] < 2:
            checkGenre[bestSong.plays_of_genre] = 2
            answer.append(bestSong.number)
    return answer


class song:
    def __init__(self, plays_of_genre, plays, number):
        self.plays_of_genre = plays_of_genre
        self.plays = plays
        self.number = number
    
    def __lt__(self, other):      
        if self.plays_of_genre > other.plays_of_genre:
            return True
        elif self.plays_of_genre == other.plays_of_genre:
            if self.plays > other.plays:
                return True
            elif self.plays == other.plays:
                return self.number < other.number
            else:
                return False
        else:
            return False
반응형

댓글