🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42579
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🔵 문제 간략화
장르 재생 횟수 > 곡 재생 횟수 > 고유 번호 순으로 정렬 후 장르 별로 최대 두 개씩 뽑아 answer에 push한 뒤 반환하면 되는 문제이다.
입력으로 들어온 장르 별 재생 횟수를 저장하기 위해 unordered_map을 사용했다.
unordered_map<장르 이름, 장르 재생 횟수>로 장르 별 재생 횟수를 누적한다.
이후 제일 많이 재생된 장르에서 우선으로 곡을 뽑으므로, value 값인 장르 재생 횟수를 기준으로 정렬하기 위해 unordered_map<장르 이름, 장르 재생 횟수>을 vector로 변환 후 장르 재생 횟수 내림차 순으로 정렬한다.
music에 대한 세부 데이터(재생 횟수, 고유 번호)가 필요하므로 struct로 music 데이터를 만들어 주고,
다시 한번 unordered_map을 사용해 (장르 - 해당 장르 곡들) 쌍을 만들어 준다.
정렬 후 장르 별로 최대 두 개씩만 뽑으면 되므로 이런 식으로 구조를 잡았다.
value 값인 해당 장르 곡들은 따로 비교 함수를 작성하여 곡 재생 횟수, 고유 번호 기준으로 정렬되게끔 했다.
모두 정렬 시키고 unordered_map<장르, 해당 장르 곡들>에서 장르 별로 접근한 다음, 해당 장르 곡들 중 첫 번째, 가능하다면 두 번째 원소 까지 answer에 push하였다.
🔵 전체 코드
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 장르 > 재생 횟수 > 고유 번호 순으로 정렬 후 장르 별로 두 개씩 뽑음
// unordered_map으로 각 장르별 재생 횟수 저장
// vector로 정렬? 위 규칙대로 함수 만들어서.
// data 생성
struct music
{
long long plays; // 재생 횟수
int i; // 고유 번호
};
unordered_map<string, long long> genresPlays;
unordered_map<string, vector<music>> musics_sorted;
bool cmp(const music& a, const music& b)
{
if (a.plays == b.plays)
return a.i < b.i;
return a.plays > b.plays;
}
vector<int> solution(vector<string> genres, vector<int> plays)
{
// 장르별 재생횟수 갱신
for (int i = 0; i < genres.size(); i++)
genresPlays[genres[i]] += plays[i];
// 음악 데이터 저장
for (int i = 0; i < genres.size(); i++)
{
music m;
m.plays = plays[i];
m.i = i;
musics_sorted[genres[i]].push_back(m);
}
for (auto& m : musics_sorted)
sort(m.second.begin(), m.second.end(), cmp);
// value 값 기준 정렬을 위해 map을 vector로 변환
vector<pair<string, long long>> genres_sorted(genresPlays.begin(), genresPlays.end());
// 플레이한 횟수가 많은 장르 별로 정렬
// 문제 조건에서 모든 장르는 재생된 횟수가 다름.
sort(genres_sorted.begin(), genres_sorted.end(), [](const pair<string, long long>& a, const pair<string, long long>& b)
{
return a.second > b.second;
});
vector<int> answer;
int idx = 0;
// 정렬된 music에서 장르 별로 최대 두 개씩 뽑음
for (const auto& genre_pair : genres_sorted)
{
string genre = genre_pair.first;
for(int i = 0; i < min(2, (int)musics_sorted[genre].size()); i++)
answer.push_back(musics_sorted[genre][i].i);
}
return answer;
}
🔵 시간 복잡도
for문으로 각 value 값을 정렬 시키는 부분이 제일 시간 복잡도가 크다.
musics_sorted의 길이는 장르의 종류이므로 최대 100이며, algorithm 헤더의 sort는 시간 복잡도가 컨테이너의 길이를 N이라 했을 때 O(NlogN)이다.
musics_sorted의 최대 길이는 100으로 작은 수여서 상수로 취급할 수 있다.
따라서 총 시간 복잡도는 O(NlogN)이다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "메뉴 리뉴얼" (0) | 2025.05.30 |
|---|---|
| [C++] Programmers Lv. 1 "신고 결과 받기" (0) | 2025.05.28 |
| [C++] Programmers Lv. 2 "오픈 채팅방" (0) | 2025.05.27 |
| [C++] Programmers Lv. 2 "할인 행사" (0) | 2025.05.24 |
| [C++] Programmers Lv. 2 "전화번호 목록" (1) | 2025.05.23 |