[Python 파이썬] 프로그래머스 - 베스트앨범

2024년 7월 17일

문제 링크 : 프로그래머스 - 베스트앨범

 

※ 만약 2번, 15번 테스트케이스가 틀리셔서 찾아오셨다면, 다음 테스트케이스를 돌려보시기 바랍니다.

genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [100, 500, 100, 100, 500]

 

 

문제 접근

 

문제에서 명시되어있듯, 핵심은 다음과 같다.

 

1. 각 장르마다 최대 2개의 노래를 앨범에 수록할 것이다.

2. 속한 노래가 많이 재생된 장르를 먼저 수록할 것이며, 각 장르에서 가장 많이 재생된 노래를 먼저 수록할 것이다. 만약 같은 장르 내에서 재생 수가 같은 노래가 존재한다면 고유 번호가 낮은 노래를 먼저 수록한다.

3. 모든 장르는 재생된 횟수가 다르다.

 

특히, 3번 덕분에 고민거리가 많이 사라졌다. 특정 두 장르의 누적 재생 횟수가 같으면 어떻게 처리해야하지..? 해서 문제를 꼼꼼히 읽어보니 3번 핵심을 발견하고 고려하지 않아도 되는구나 싶었다.

 

결국 문제를 풀기 위해선 다음과 같은 작업이 순차적으로 필요하다.

① 각 장르별 누적 재생 수를 구하고, 또한 같은 장르끼리 노래들을 묶어주어야 함.

② 각 장르별 누적 재생 수를 정렬하고, 또한 각 장르끼리 노래들을 묶은 집합 안에서도 정렬해주어야 함. 정렬 우선순위는 재생 수이며, 후순위는 고유 번호이다. 재생 수가 같다면 작은 고유 번호가 우선순위를 가진다.

③ 1번, 2번 과정을 마쳤다면 장르 별로 누적 재생 수가 많은 장르부터 최대 2개씩 노래를 선택한다. 각 장르에서도 가장 재생을 많이 한 노래를 선택하며, 재생 수가 같다면 고유 번호가 작은 노래를 선택한다.

 

 

여기서 나는 데이터 파싱 및 클러스터링을 얼마나 잘하느냐를 묻는 문제라고 생각했다.

 

주어진 데이터를 어떻게 가공해서 내가 다루기 쉽도록 파싱을 하느냐에 따라 문제의 난이도가 갈린다고 본다.

 

아래 전체 코드 중에서, 위 ① ~ ③을 구현한 코드는 다음과 같다.

 

① 각 장르별 누적 재생 수를 구하고, 또한 같은 장르끼리 노래들을 묶어주어야 함.

 

# 장르 별 누적 재생 수를 카운트하기 위한 딕셔너리
genresPlayDict = {}

# 같은 장르끼리 묶기 위한 딕셔너리
genresDict = {}

for idx in range(len(genres)):
    if genres[idx] in genresDict:
        genresDict[genres[idx]].append([idx, plays[idx]])
        genresPlayDict[genres[idx]] += plays[idx]

    else:
        genresDict[genres[idx]] = [[idx, plays[idx]]]
        genresPlayDict[genres[idx]] = plays[idx]

 

 

② 각 장르별 누적 재생 수를 정렬하고, 또한 각 장르끼리 노래들을 묶은 집합 안에서도 정렬해주어야 함. 정렬 우선순위는 재생 수이며, 후순위는 고유 번호이다. 재생 수가 같다면 작은 고유 번호가 우선순위를 가진다.

 

# 누적 재생 수를 기준으로 모든 장르를 정렬한 결과를 담기 위한 배열
genresSortByTotalPlays = []

for key, value in genresPlayDict.items():
    genresSortByTotalPlays.append([key, value])

# 누적 재생 수 기반 정렬
genresSortByTotalPlays.sort(reverse=True, key=lambda x: x[1])


# 같은 장르끼리 클러스터링한 노래들 중에서 정렬한 결과를 담기 위한 배열
genresSortByPlays = []

for key, value in genresDict.items():
    genresSortByPlays.append([key, value])

# genreㄴCnt = 장르 종류 가짓수
genresCnt = len(genresSortByPlays)

# 각 장르 내에서 재생 수 기준 오름차순, 같다면 인덱스 번호 기준 내림차순
# 이렇게 정렬하면 genresSortByPlays에서 pop() 하여 우선순위가 높은 노래 순으로 추출 가능
for i in range(genresCnt):
    temp = genresSortByPlays[i][1]
    # 각 장르별로 재생 수 기반 오름차순, 재생 수가 같다면 인덱스 번호 기준 내림차순
    temp.sort(key = lambda x:( x[1], -x[0] ))
    genresSortByPlays[i][1] = temp

 

 

③ 1번, 2번 과정을 마쳤다면 장르 별로 누적 재생 수가 많은 장르부터 최대 2개씩 노래를 선택한다. 각 장르에서도 가장 재생을 많이 한 노래를 선택하며, 재생 수가 같다면 고유 번호가 작은 노래를 선택한다.

 

# 베스트앨범 노래들을 담을 배열
answer = []

# genresCnt = 장르 종류 가짓수
for i in range(genresCnt):
	# 누적 재생 수가 많은 장르의 노래가 최우선순위
    nowGenre = genresSortByTotalPlays[i][0]
    # 같은 장르끼리 클러스터링한 배열에서 현재 수록하고 싶은 장르를 탐색
    for j in range(genresCnt):
        if genresSortByPlays[j][0] == nowGenre:
            cnt = 0
            # 베스트앨범에는 같은 장르를 최대 2개 수록 가능함 and 2개 이하라면 1개만 수록하도록 함
            while cnt < 2 and genresSortByPlays[j][1]:
            	# 각 장르에서 베스트앨범에 우선순위로 수록될 노래를 추출하여 answer에 추가함
                answer.append(genresSortByPlays[j][1].pop()[0])
                cnt += 1
            break

 

 

---

전체 코드

 

def solution(genres, plays):
    # 장르 별 누적 재생 수를 카운트하기 위한 딕셔너리
    genresPlayDict = {}

    # 같은 장르끼리 묶기 위한 딕셔너리
    genresDict = {}

    for idx in range(len(genres)):
        if genres[idx] in genresDict:
            genresDict[genres[idx]].append([idx, plays[idx]])
            genresPlayDict[genres[idx]] += plays[idx]

        else:
            genresDict[genres[idx]] = [[idx, plays[idx]]]
            genresPlayDict[genres[idx]] = plays[idx]

    # 누적 재생 수를 기준으로 모든 장르를 정렬한 결과를 담기 위한 배열
    genresSortByTotalPlays = []

    for key, value in genresPlayDict.items():
        genresSortByTotalPlays.append([key, value])

    # 누적 재생 수 기반 정렬
    genresSortByTotalPlays.sort(reverse=True, key=lambda x: x[1])

    # 같은 장르끼리 클러스터링한 노래들 중에서 정렬한 결과를 담기 위한 배열
    genresSortByPlays = []

    for key, value in genresDict.items():
        genresSortByPlays.append([key, value])

    # genreCnt = 장르 종류 가짓수
    genresCnt = len(genresSortByPlays)

    # 각 장르 내에서 재생 수 기준 오름차순, 같다면 인덱스 번호 기준 내림차순
    # 이렇게 정렬하면 genresSortByPlays에서 pop() 하여 우선순위가 높은 노래 순으로 추출 가능
    for i in range(genresCnt):
        temp = genresSortByPlays[i][1]
        # 각 장르별로 재생 수 기반 오름차순, 재생 수가 같다면 인덱스 번호 기준 내림차순
        temp.sort(key=lambda x: (x[1], -x[0]))
        genresSortByPlays[i][1] = temp

    # 베스트앨범 노래들을 담을 배열
    answer = []

    # genresCnt = 장르 종류 가짓수
    for i in range(genresCnt):
        # 누적 재생 수가 많은 장르의 노래가 최우선순위
        nowGenre = genresSortByTotalPlays[i][0]
        # 같은 장르끼리 클러스터링한 배열에서 현재 수록하고 싶은 장르를 탐색
        for j in range(genresCnt):
            if genresSortByPlays[j][0] == nowGenre:
                cnt = 0
                # 베스트앨범에는 같은 장르를 최대 2개 수록 가능함 and 2개 이하라면 1개만 수록하도록 함
                while cnt < 2 and genresSortByPlays[j][1]:
                    # 각 장르에서 베스트앨범에 우선순위로 수록될 노래를 추출하여 answer에 추가함
                    answer.append(genresSortByPlays[j][1].pop()[0])
                    cnt += 1
                break

    return answer

if __name__ == "__main__":
    genres = ["classic", "pop", "classic", "classic", "pop"]
    plays = [100, 500, 100, 100, 500]

    print(solution(genres, plays))

---

풀이 후기

 

머신러닝을 학습할 때, 주어진 데이터를 내가 원하는 방향으로 사용할 수 있도록 가공하는 작업이 최우선적으로 진행되었던 기억이 있다.

그때에 비하면 양반이지만 오랜만에 머신러닝을 처음 학습할 때가 생각나는 문제였다.