[프로그래머스] 베스트앨범

문제 설명

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

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

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

제한사항

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

입출력 예

 

genres : [classic, pop, classic, classic, pop]

plays: [500, 600, 150, 800, 2500]

return : [4, 1, 3, 0]

입출력 예 설명

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]번 노래를 그다음에 수록합니다.

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

 

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct Song {

    string genres;
    int plays;
    int total;
    int index;

    Song(string a, int b, int c, int d)
    {   
        genres = a;
        plays = b;
        total = c;
        index = d;
    }

    bool operator<(const Song& ss) const {
        if (total > ss.total)
        {
            return true;
        }
        else if (total == ss.total)
        {
            if (plays > ss.plays)
            {
                return true;
            }
            else if (plays == ss.plays)
            {
                if (index < ss.index)
                {
                    return true;
                }
                else 
                    return false;
            }
            else 
                return false;
        }
        else 
            return false;
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> m;
    vector<Song> v;
    int size = genres.size();

    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];  //기존에 값이 없더라도 이렇게만 처리해도 된다.
     }

    for (int i = 0; i < size; i++)
    {
        v.push_back(Song(genres[i],plays[i],m[genres[i]],i));
    }

    sort(v.begin(), v.end());

    
    int cnt = 2;

    for (int i = 0; i < size; i++)
    {
        if (cnt == 0)
        {
            if (v[i].genres == v[i-1].genres)
                continue;
            else
            {
                cnt = 2;
                answer.push_back(v[i].index);
                cnt--;
                continue;
            }
        }
        if (cnt == 1 && (v[i - 1].genres != v[i].genres))
        {
            cnt = 2;
            answer.push_back(v[i].index);
            cnt--;
            continue;
        }
        else
        {
            answer.push_back(v[i].index);
            cnt--;
        }
    }

    return answer;
}

operator랑 struct를 연습하는 좋은 문제,

hash를 연습할 수 있는 좋은 문제

 

(hash가 값이 없더라도 map[key]+=value; 로 취한다면 값이 생김)

---

int cnt=2;
for (int i = 0; i < size; i++)
    {
        if (cnt == 0)
        {
            if (v[i].genres == v[i-1].genres)
                continue;
            else
            {
                cnt = 2;
                answer.push_back(v[i].index);
                cnt--;
                continue;
            }
        }
        if (cnt == 1 && (v[i - 1].genres != v[i].genres))
        {
            cnt = 2;
            answer.push_back(v[i].index);
            cnt--;
            continue;
        }
        else
        {
            answer.push_back(v[i].index);
            cnt--;
        }
    }

아래코드만 좀 뗴서 보면

 

2개의 앨범만 추출한다.

1개일땐 그냥 추출한다.

 

조건때문에 만든 코드인데 정리가 좀 안된다.

 

cnt는 2로 시작하고 노래 index를 solution에 넣을 때마다 하나씩 빼준다.

만약 cnt가 0이라면 (동일한 노래 두 개를 다 뺀 것)

다음 새로운 노래가 나올때까지 (현재장르랑 이전장르랑 다를 때까지)계속 continue해준다.

 

만약, 다른 노래가 나온다면 다시 cnt를 2로 해주고

그 해당하는 새로운 노래를 index를 추출해준다.

그리고 다시 cnt--;

 

그런데 노래가 1개일 때를 봐야 하는데,

만약 cnt==1이면서 (바로 전 노래가 이미 하나가 추출 된 상태)

현재노래랑 예전노래랑 다르다면 (바로전 노래가 1개만 있었던 상태)

cnt를 2로 바꾸어주고 다시 현재노래를 뺴준다.

 

---

 

깔끔하지 않지만 현재 생각나는게 이렇게밖에 구현이 안돼서 급한대로 풀었다.

돌아가긴 잘 돌아간다. 더 수정을 해야할 것 같다.