[고득점Kit][해시] 베스트 앨범 ⭐⭐⭐

[해시] 베스트 앨범

난이도 ⭐⭐⭐

문제

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

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 
베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

📢 제한사항

- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.

내 풀이

장난하냐고!!!!!!!!!!!!!! ㅠ ㅠ 이 문제를 푸는데 이틀이나 걸렸다. 뭔가 이렇게 풀면 될 것 같으면서도 코드로 풀어내는게 너무 어려웠고 머리가 하얘지는 기분이였다. 내가 이렇게 머리가 안좋은가? 싶어 좌절의 연속이였고 그러다 취업에 대한 불안감까지 엄습하여 컴퓨터 앞에서 폭풍 오열 😭😭 공부하다가 울어보기는 난생 처음이였다. 근데 결국엔 풀어내서 너무너무 기뻤다 !!!!!!!!!!!!!! 테스트 케이스 전부 통과했을 때의 그 기쁨이란.. 😁

일단 코딩테스트 초보이기 때문에.. 효율적으로 알고리즘을 짜기 위한 고민은 일단 제쳐두고 직관적으로, 단순하게 생각하는 것이 중요한 것 같다. 일단 초보니까 변수를 많이 두더라도, 컨테이너를 많이 두더라도, 공간적인 효율성은 제쳐 두고 일단 쉽게 쉽게 딱 직관적으로 생각하도록 하자!

그리고 머리가 안돌아가면 일단 그 문제는 미뤄두고 다른 문제를 먼저 푸는 것도 도움이 되는 것 같다. 이 문제 이틀간 붙잡고 있다가 스택/큐 문제 하나 풀고 오니 갑자기 어떻게 풀면 되겠다는 생각이 떠오르길래 놀라웠따..

그리고 내가 생각한 알고리즘이 있는데 그것을 코드로 구현하기 힘들 때 해당 알고리즘을 쉽게 구현할 수 있도록 도와주는 라이브러리가 있는지 구글링 해서 알아보도록 하자! sort 함수는 무조건 오름차순 정렬만 되는건 줄 알았어서 ‘내림차순 + 장르별 플레이 타임 rank’ 를 기준으로 도대체 어떻게 직접 정렬을 구현 해야할까 싶어 멘붕이 왔었는데 구글링을 통해 비교 함수를 직접 사용자 정의로 구현하고 sort함수에 그 함수 포인터를 넘겨주는 방식으로 내가 원하는 방식대로 정렬할 수 있다는 사실을 알게 되었고 그 이후로 좀 풀이가 수월해졌던 것 같다. 난 알고리즘 공부를 이제 막 시작한 단계라 라이브러리들에 대해서도 많이 모르니까 자존심 때문에 내내 붙잡고 있지 말고 ㅋㅋㅋㅋㅋㅋㅋ 모르겠으면 구글링 해서 공부하고 스킬을 쌓아나가면 된다…. 잘할 수 있어. 화이팅 😀

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare1(pair<string, int> a, pair<string, int> b) // const & 을 없애야 함. 템플릿이라서
{
	return a.second > b.second;
}

bool compare2(pair<string, pair<int, int>> a, pair<string, pair<int, int>> b)
{
	if (a.second.second == b.second.second)
		a.second.first < b.second.first;
	return a.second.second > b.second.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;

	unordered_map<string, int> genre_count;
	unordered_map<string, int> plays_sum;

	vector<pair<string, int>> genre_rank;
	vector<pair<string, pair<int, int>>> temp;
	vector<pair<string, pair<int, int>>> ordered;

	for (int i = 0; i < genres.size(); i++)
	{
		genre_count[genres[i]]++;

		if (plays_sum.find(genres[i]) == plays_sum.end())
		{
			plays_sum[genres[i]] = plays[i];
		}
		else
		{
			plays_sum[genres[i]] = plays_sum[genres[i]] + plays[i];
		}
	}

	for (auto & elem : plays_sum)
	{
		genre_rank.push_back(elem);
		sort(genre_rank.begin(), genre_rank.end(), compare1);
	}

	for (int i = 0; i < genre_rank.size(); i++)
	{
		for (int j = 0; j < genres.size(); j++)
		{
			if (genres[j] == genre_rank[i].first)
			{
				temp.push_back(make_pair(genres[j], make_pair(j, plays[j])));
			}
      sort(temp.begin(), temp.end(), compare2);
		}
		
		for (int k = 0; k < 2; k ++)
		{
		    answer.push_back(temp[k].second.first);
		    if (temp.size() == 1)
		        break;
		}
		
		temp.clear();
	}

	return answer;
}

• 입출력 예시
  • 입력
    • genre [classic, pop, classic, classic, pop]
    • plays [500, 600, 150, 800, 2500]
  • 출력
    • answer [4, 1, 3, 0]
• 구조
  • genre_count : 장르 이름이 Key로 들어가고 장르에 해당하는 곡의 개수가 Value로 들어가는 Hash Map
    • [classic] = 3, [pop] = 2

      genre_count[genres[i]]++;
      

  • plays_sum : 장르 이름이 Key로 들어가고 각각 장르마다 플레이 타임의 총 합이 Value로 들어가는 Hash Map
  • [classic] = 1450, [pop] = 3100

    // 처음 들어갈 때
    plays_sum[genres[i]] = plays[i];
    // 그 외
    plays_sum[genres[i]] = plays_sum[genres[i]] + plays[i];
    

  • genre_rank : 총 플레이타임이 가장 큰 장르일 수록 맨 앞에 오도록 내림 차순 정렬된 벡터
  • 먼저 plays_sum의 원소들을 복사하여 삽입
  • sort에 사용될 비교함수로 compare1 을 정의하였고 이를 이용하여 genre_rank를 원소(pair)의 second인 총 플레이타임에 의한 내림차순 정렬을 해주었다.
  • (pop ,3100), (classic, 1450)

    sort(genre_rank.begin(), genre_rank.end(), compare1);
    

  • temp
    • genre_rank에서 정렬될 원소 순서들, 즉 플레이타임이 가장 큰 장르일 수록 앞에 오는 이 벡터를 사용하여 인수로 받은 genres와 plays에서 그에 대응 하는 (장르이름, 플레이타임, 인덱스)을 원소로 받는 벡터
    • sort에 사용될 비교함수로 compare2 을 정의하였고 이를 이용하여 temp를 원소(pair)의 second의 second인 그냥 각각의 플레이타임에 의한 내림차순 정렬을 해주었다.
      • 플레이 타임(second.second)이 같을 경우 인덱스에 의한(second.first) 오름차순 정렬
    • (pop, (2500, 4)), (pop, (600, 1)), (classic, (800, 3)), (classic, (500, 0)), (classic, (150, 2))
  • answer
    • temp에서 각 장르별로 2 개씩만 잘라서 answer에 인덱스를 추가한다.
      • 곡이 1개밖에 없는 장르는 1개만.
    • 4, 1, 3, 0 👈 최종 답

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기