못해도 하루에 한 문제씩은 꼭 풀어보려고 노력하는 중입니다!
오늘은 고득점 kit 해시 파트의 마지막 문제를 들고 왔습니다!
목차
0. 문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
0.0. 제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
0.1. 입출력 예
| genres | plays | return |
| [classic, pop, classic, classic, pop] | [500, 600, 150, 800, 2500] | [4, 1, 3, 0] |
0.2. 입출력 예 설명
classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
- 고유 번호 3: 800회 재생
- 고유 번호 0: 500회 재생
- 고유 번호 2: 150회 재
pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
- 고유 번호 4: 2,500회 재생
- 고유 번호 1: 600회 재생
따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.
1. 풀이 과정
Level 3에 압도되지 않고 차근차근 생각해보면 충분히 풀만한 문제였습니다.
아래 A4용지에 적은 것과 동일하게 세 가지 단계로 나눠서 풀었습니다.
첫 번째는 map을 이용해서 각 genres의 재생 횟수를 구했습니다.
genres를 key로 받아서 plays값들을 value로 계속 더해주는 형식으로 구현하였습니다.
두 번째는 map은 key값을 기준으로 오름차순으로 정렬하기 때문에
value값을 기준으로 내림차순으로 정렬하기 위해서는 따로 조작이 필요합니다.
vector를 하나 만들어서 map의 값들을 복사해준 후에 plays를 기준으로 내림차순으로 정렬했습니다.
저는 cmp라는 bool타입 함수를 만들어서 했지만, 람다함수를 이용해서 solution 함수 내에서 해결할 수도 있습니다.
세 번째는 정렬한 vector의 순서대로 각 genres에서 가장 많이 재생된 곡(index)과 두 번째로 많이 재생된 곡을 찾아서 answer에 넣어줍니다. 이 과정에서 play값과 index값을 따로 저장해서 비교할 수 있도록 만들었습니다.
이 문제를 해결 할 때의 Big-O notation은 이중for문을 사용했기 때문에 O(N^2)이 되겠습니다.
2. 소스 코드
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool cmp(pair<string,int> a, pair<string,int> b){
return a.second > b.second;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
map<string,int> m;
int size = genres.size();
// 1. genres의 재생 횟수 구하기
for(int i = 0; i < size; ++i){
if (m.find(genres[i]) == m.end())
m.insert(make_pair(genres[i], plays[i]));
else
m[genres[i]] += plays[i];
}
// 2. plays(map의 value값)를 기준으로 정렬
vector<pair<string,int>> v(m.begin(), m.end()); // iterator와 for문을 사용하는 것보다 훨씬 효과적!
sort(v.begin(), v.end(), cmp);
// 3. genres에서 v에 있는 genres를 순서대로 찾은 후 play수가 많은 1가지 혹은 2가지 값을 answer에 넣기
for (int i = 0; i < v.size(); ++i){
int f = 0; // 그 장르에서 가장 큰 값의 play
int fi = 0; // 그 장르에서 가장 큰 값의 index
int s = 0; // 그 장르에서 두 번째로 큰 값의 play
int si = 0; // 그 장르에서 두 번째로 큰 값의 index
for (int j = 0; j < size; ++j){ // 계속 비교하면서 그 장르에서 plays가 가장 큰 값, 두 번째로 큰 값, 값들의 index를 저장
if (genres[j] == v[i].first){
if (plays[j] > f){
s = f; // 밀리는 부분도 체크!!
si = fi; // 밀리는 부분도 체크!!
f = plays[j];
fi = j;
}
else if (plays[j] > s){
s = plays[j];
si = j;
}
}
}
answer.push_back(fi);
if(s > 0) // 두 번째 값이 존재하면 두 번째 값도 넣어준다
answer.push_back(si);
}
return answer;
}
3. 후기
한번 풀었던 문제임에도 불구하고 1시간 30분이 걸렸습니다.
처음에 집중하지 못하고 이리저리 헤멘게 30분,
map을 sort하는 것을 까먹어서 검색하는 데에 30분,
마지막에 f에 있던 값이 s로 밀리는 것을 생각하는 것을 까먹어서 그 오류 찾는데 30분 정도 사용한 것 같습니다.
복습의 중요성을 뼈저리게 느끼고 갑니다.
조만간 아직 익숙하지 않은 STL들을 한번 쭉 정리해야 새로운 타입의 문제를 푸는 시간을 줄일 수 있어보입니다.
출처 : 프로그래머스 코딩테스트 연습, programmers.co.kr/learn/courses/30/lessons/42579
최근댓글