Programmers 코딩테스트 연습 베스트 앨범 Python 정답.

정렬이 무엇인지 제대로 보여주는 좋은 문제라고 생각한다.

 

딱히 복잡한 알고리즘이 아닌. 논리적인 사고로 문제를 설명하는 연습을 하게 해준다.

 

초기화: 

 

for문에서는 장르와 재생 횟수 dict {장르:  재생횟수}

장르에 들어갈 곡정보를 튜플로 만들어 {장르 : [튜플 리스트]} 튜플 (곡 id, 재생횟수)

 

1. 먼저 key value dictionary를 만들어 value로 장르를 정렬한 리스트를 keys를 통해 만든다.

(내부 원소들은... 장르 이름 str들)

 

2. 이 key(장르 이름 str)들 순서대로 장르: 튜플 (곡 id, 재생횟수)를 정렬하여 결과 list에 원소들을 extend 해준다.

 (곡 id, 재생횟수)

(-x[1],x[0])은 먼저 재생횟수 기준으로 내림차순 정렬, 그 이후 곡 id 기준 오름차순 정렬을 의미한다.

from _collections import defaultdict


# zip에서 활용하기 위해 정의한 generator
def idGenerator():
    id = 0
    while True:
        yield id
        id += 1


def solution(genres, plays):
    # 값 초기화 없이 활용하기 위해 defaultdict을 사용한다.
    genre_plays = defaultdict(lambda :0)
    genre_SongsWithId = defaultdict(list)

    # zip 안에는 iterable한 객체만 사용할 수 있다.
    for song_id, genre, play in zip(idGenerator(), genres, plays):
        genre_plays[genre] += play
        genre_SongsWithId[genre].append((song_id, play))
        #삽입시 정렬은 퀵소트의 시간복잡도를 망칩니다.

    #key값을 정렬하여 리스트를 만들어준다.
    sortedGenre = sorted(genre_plays.keys(),
                         key= lambda x: genre_plays[x],
                         reverse=True)

    # 정답을 담을 List를 정의한다.
    answer = []

    # 정렬 결과를 출력해보자. 또한 위의 로직으로 곡의 정렬 리스트 출력.
    for genre in sortedGenre:
        print(genre +"장르의 재생 횟수 : "+ str(genre_plays[genre]))
        #정렬 결과를 answer에 append
        print(genre +"장르에 속한... 정보 : "+ str(genre_SongsWithId[genre]))
        answer.extend([song_id for song_id, play in sorted(genre_SongsWithId[genre], key=lambda x: (-x[1], x[0]))[:2]])

    return answer

 

시간 복잡도를 분석해보면 정렬 nlogn. 첫번째 for문 n.

두번째 for문의 경우 nlogn정렬 후 n의 탐색 -> nlogn * 바깥 n 이므로

n^2*logn의 시간이 걸릴 것이다.

 

n번 순회하면서 nlogn의 정렬을 해야 하므로... 이 시간 복잡도는 피할 수 없을 것 같다.. ㅋㅋ

 

#heapq를 사용해서 삽입 시의 시간 복잡도를 logn으로 줄여서 nlogn의 시간 복잡도를 만들 수 있지 않을까?