20240229_베스트앨범(프로그래머스)

오늘의 TIL은 베스트앨범이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려고 한다.

노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 아래와 같다.

 

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.

 

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수배열 plays가 주어질 때,

베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하시오.

 

 

제한 조건

genres[i]는 고유번호가 i인 노래의 장르이다.

plays[i]는 고유번호가 i인 노래가 재생된 횟수이다.

genres와 plays의 길이는 같으며, 이는 1 이상, 10,000 이하이다.

장르의 종류는 100개 미만이다.

장르에 속한 곡이 하나라면, 하나의 곡만 선택한다.

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

 

 

해결 방안

처음에 문제를 보고 생각난 아이디어는

 

장르별로 재생횟수를 더해서 재생횟수 순으로 정렬된 장르를 구하고,

각 장르의 곡마다 재생횟수가 많은 순서대로 정렬하여 곡을 기록해놓은 후에

위의 정보들을 종합하여 장르별로 2곡씩 뽑느 작업을 진행하면 된다고 생각하였다.

 

그러나 이 과정에서 여러 정보들을 나눠서 관리하면 해당하는 정보의 인덱스가 달라질 수 있기 때문에

이를 한 번에 관리하는 구조체의 필요성을 느끼게 되었다.

 

다시 말해서 하나의 곡에는 해당하는 장르, 재생횟수, genres에서의 인덱스를 갖고 있어야 하는 것을 알 수 있다.

이를 통해서 곡마다 위의 세 정보를 가지는 클래스로 만들어서 관리하면 쉽게 해결할 수 있을 것이라고 판단할 수 있다.

또, 이 곡을 가지고 나누고, 선택하고, 정렬하는 과정에서 Linq의 기능을 사용하면 편하게 작업을 진행할 수 있다.

 

 

통과한 답안

using System;
using System.Collections.Generic;
using System.Linq;

public class Song
{
    public string Genre { get; set; }
    public int Plays { get; set; }
    public int Index { get; set; }

    public Song(string genre, int plays, int index)
    {
        Genre = genre;
        Plays = plays;
        Index = index;
    }
}

public class Solution {
    public int[] solution(string[] genres, int[] plays) {
        int[] answer = new int[] {};
        List<Song> songs = new List<Song>();
        for (int i = 0; i < genres.Length; i++)
        {
            songs.Add(new Song(genres[i], plays[i], i));
        }

        var genrePlayCounts = songs.GroupBy(song => song.Genre)
                                   .Select(group => new
                                   {
                                       Genre = group.Key,
                                       TotalPlay = group.Sum(song => song.Plays)
                                   })
                                   .OrderByDescending(genre => genre.TotalPlay);

        List<int> bestAlbum = new List<int>();
        foreach (var genre in genrePlayCounts)
        {
            var songsInGenre = songs.Where(song => song.Genre == genre.Genre)
                                    .OrderByDescending(song => song.Plays)
                                    .ThenBy(song => song.Index)
                                    .Take(2);
            bestAlbum.AddRange(songsInGenre.Select(song => song.Index));
        }

        answer = bestAlbum.ToArray();
        
        return answer;
    }
}

 

 

Song 클래스 생성

public class Song
{
    public string Genre { get; set; }
    public int Plays { get; set; }
    public int Index { get; set; }

    public Song(string genre, int plays, int index)
    {
        Genre = genre;
        Plays = plays;
        Index = index;
    }
}

 

필요한 정보들을 가지는 Song이라는 클래스를 생성하여 정의한다.

 

 

Songs 리스트 만들기

List<Song> songs = new List<Song>();
for (int i = 0; i < genres.Length; i++)
{
    songs.Add(new Song(genres[i], plays[i], i));
}

 

genres 배열로 주어지는 Song들을 담기 위한 Songs 리스트를 만든다.

 

 

Song을 장르별로 재생횟수를 더하기

var genrePlayCounts = songs.GroupBy(song => song.Genre)
                           .Select(group => new
                           {
                               Genre = group.Key,
                               TotalPlay = group.Sum(song => song.Plays)
                           })
                           .OrderByDescending(genre => genre.TotalPlay);

 

genrePlayCounts를 정의하여 songs들을 Genre에 따라 그룹을 나누고,

각 장르의 총 재생 횟수를 계산한 다음, 그 결과를 총 재생 횟수가 높은 순으로 정리한다.

여기서 사용한 Linq의 GroupBy, Select, OrderByDescending은 Linq에서도 자주 사용되는 기능들이다.

 

 

bestAlbum 리스트에 담기

List<int> bestAlbum = new List<int>();
foreach (var genre in genrePlayCounts)
{
    var songsInGenre = songs.Where(song => song.Genre == genre.Genre)
                            .OrderByDescending(song => song.Plays)
                            .ThenBy(song => song.Index)
                            .Take(2);
    bestAlbum.AddRange(songsInGenre.Select(song => song.Index));
}

 

새로운 리스트 bestAlbum 리스트를 만든 후에 Linq를 이용해서 문제의 조건에 맞게 song을 담는다.

위에서 선언한 genrePlayCounts의 각 genre에 대해서 재생횟수가 많은 순서대로 2개씩 뽑는데

Linq의 Where, OrderByDescending, ThenBy, Take(2)를 사용하였다.

 

songs 리스트에서 현재의 장르와 같은 곡들을 뽑아낸(Where) 후에

이를 재생 횟수가 많은 순서대로 정렬(OrderByDescending)하고

만약 재생 횟수가 같은 노래가 여러 개인 경우에는 고유 번호가 낮은 순으로 재 정렬(ThenBy)하고

정렬된 곡들 중에서 2곡까지 선택(Take(2))한다.

 

이를 모든 장르에 대해서, 재생 횟수가 많은 장르부터 수행하므로, 문제의 조건에 만족하는 bestAlbum이 만들어지게 된다.

마지막으로 이렇게 만들어진 List를 배열화하여 answer로 만들면 주어진 조건에 맞는 답을 구할 수 있게 된다.

 

 

오늘은 베스트앨범이라는 겉에서 접근하기에 흥미를 끄는 문제를 선택하여 풀게 되었는데,

유니티를 통한 게임 등을 만드는 경우에는 자주 사용해서 친근했지만,

알고리즘 문제를 푸는 경우에는 거의 사용하지 않았었던 클래스를 사용하여 풀이하게 되었다.

 

문제를 푸는 과정에서 처음에는 접근이 용이해보였지만,

장르, 재생횟수, 인덱스라는 3개의 데이터를 갖는 구조체를 만들어야되는데

Dictionary나 HashSet을 사용하기에 애매한 느낌이 있어서 어떻게 풀이해야되나 고민했었는데,

이는 클래스를 만들어서 사용하면 된다는 점을 깨달아서 이를 기록하기 위해 TIL로 작성하게 되었다.