23.09.17. 풀었던 문제들

Programmers Lv. 3 베스트앨범, 15분

 그냥 풀면 되는 구현 문제. 

1. 장르별 재생회수의 순서
2. 장르 내부에서 재생회수의 순서

 위 2가지에 대해 정렬되어 있어야 하기 때문에 map을 2개 써야 한다. 그냥 뭐.. map에 genre를 key로 넣어 재생회수 합계와 해당 genre에 속한 노래들의 {재생회수, index}를 저장하면 된다.

int len;
 
struct Info{
    int play, index;
};
 
struct cmp{
    // 조건 1. play가 큰 것.
    // 조건 2. index가 작은 것.
    bool operator()(Info &a, Info &b){
        if(a.play == b.play) return a.index > b.index;
        return a.play < b.play;
    }
};
 
typedef pair<string, int> psi;
 
bool cmpMap(psi &a, psi &b){
    if(a.second == b.second) return a.first < a.first;
    return a.second > b.second;
}
 
vector<int> solution(vector<string> genres, vector<int> plays) {
    len = plays.size();
    
    // 1. 장르별 재생회수
    map<string, int> genrePlay; // genrePlay[i] : genre i의 재생 회수
    // 2. 장르 내부에서 재생회수 
    map<string, priority_queue<Info, vector<Info>, cmp>> genrePlayMap; // genrePlayMap[i] : genre i의 plays pa
    for(int i = 0; i<len; i++){
        string genre = genres[i];
        int play = plays[i];
        
        genrePlay[genre] += play;
        
        Info info; info.index = i; info.play = play;
        genrePlayMap[genre].push(info);
    }
    
    // map value로 정렬
    vector<psi> genrePlays(genrePlay.begin(), genrePlay.end());
    sort(genrePlays.begin(), genrePlays.end(), cmpMap);
    
    vector<int> answer;
    for(psi data : genrePlays){
        string genre = data.first;
        
        priority_queue<Info, vector<Info>, cmp> &pq = genrePlayMap[genre];
        answer.push_back(pq.top().index); pq.pop();
        if(!pq.empty()) answer.push_back(pq.top().index);
    }
    
    return answer;
}

 

시간복잡도

 for문이 O(n). map size는 worst case O(n)이므로 insert/pop에 O(nlogn)이 걸린다. 정렬에는 O(nlogn). 총 합계 O(nlogn)이다.

 

후기

 굳이 pq로 안하고 vector로 넣은 다음에 한 번에 정렬했어도 됐을 것 같다.

 

 

 

Programmers Lv. 3, 스티커 모으기(2), 18분

 전형적인 DP 문제.

 문제를 딱 보면 dp[i]를 i번째 스티커까지 봤을 때 최댓값으로 둘 지, i번째까지 보고 i번째 스티커를 떼었을 때 최댓값이라고 정의할지 고민이 조금 된다. 그러나 후자로 선택하면 뗀다는 정보가 추가적으로 필요하기에 복잡해진다. 전자로 선택하면 된다.

 그러면 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])가 된다. 후항은 dp[i-2]에서 sticker를 떼든 말든 상관없이 i번째 스티커를 뗄 수 있기 때문이고, 전항은 i-1번째 스티커를 떼었는지 여부는 모르기 때문이다.

 

 또 하나, 유의해야 할 것이 있는데 이 문제는 선형이 아니라 환형이기 때문에 0번째 스티커를 떼는 경우와 0번째 스티커를 떼지 않는 경우를 고려해야 한다. 전자의 경우에는 마지막 스티커를 뗄 수 없고, 후자의 경우는 마지막 스티커를 뗄 수 있으므로 dp 연산을 어디까지 할지 지정만 잘 해주면 된다.

int len;
 
int solution(vector<int> sticker)
{
    len = sticker.size();
    if(len <= 2) return *max_element(sticker.begin(), sticker.end());
    
    vector<int> dp(len, 0);
    
    // case 1. 0번째 것 뜯는 경우
    dp[0] = sticker[0];
    dp[1] = dp[0];
    for(int i = 2; i<len-1; i++){
        dp[i] = max(dp[i-1], sticker[i] + dp[i-2]);
    }
    int answer = *max_element(dp.begin(), dp.end());
    
    // case 2. 0번째 것 뜯지 않는 경우
    fill(dp.begin(), dp.end(), 0);
    dp[0] = 0;
    dp[1] = sticker[1];
    for(int i = 2; i<len; i++){
        dp[i] = max(dp[i-1], sticker[i] + dp[i-2]);
    }
    answer = max(answer, *max_element(dp.begin(), dp.end()));
 
    return answer;
}

 

시간복잡도

 O(n) 순회를 2번 하므로 O(n)