[코딩테스트 고득점 Kit] 해시 5 - 베스트앨범

코딩테스트 연습 - 베스트앨범

프로그래머스

 

역시나 HashMap을 이용하여 푸는 문제

HashMap을 하나만 쓰고도 해결할수 있겠지만 그렇게 되면 코드봤을때 깔끔하고 명쾌한 느낌은 아닐것 같아서 HashMap 여러개를 사용하기로 한다.

1. 장르1순위 HashMap : (key) 장르이름 + 1 — (value) [노래순번, 재생횟수]
2. 장르2순위 HashMap : (key) 장르이름 + 2 — (value) [노래순번, 재생횟수]
3. 장르노래재생 HashMap : (key) 장르이름 — (value)장르노래재생수

알고리즘은 대략 아래와 같다.

1. 해당 장르 노래 재생 횟수를 추가한다.
2. 해당 장르의 1순위와 재생횟수를 비교한다.
   1.  재생횟수가 1순위보다 크면 현재 1순위는 2순위로 밀려나고 1순위에 현재 노래를 정보를 저장한다.
3. 해당 장르 1순위보다 재생횟수가 작으면 2순위와 비교한다.
   1. 재생횟수가 2순위보다 크면 2순위에 현재 노래정보를 저장한다.
4. 노래재생 횟수에 따라 장르를 정렬한다.
5. 정렬된 장르의 1순위,2순위를 각 출력한다.

JAVA

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        HashMap<String, Integer[]> gFirst = new HashMap<String, Integer[]>();   //장르별 1위
        HashMap<String, Integer[]> gSecond = new HashMap<String, Integer[]>();  //장르별 2위
        HashMap<String, Integer> gCount= new HashMap<String, Integer>();    //장르별 재생횟수
        
        for(int i=0; i<genres.length; i++){
            //장르별 재생횟수
             if(gCount.containsKey(genres[i])){
                 gCount.put(genres[i], gCount.get(genres[i]) +  plays[i]);
             }else{
                 gCount.put(genres[i], plays[i]);
             }
            Integer[] music = {i, plays[i]};
            //장르별 1위 비교
             if(gFirst.containsKey(genres[i])){
                 if(gFirst.get(genres[i])[1] < plays[i]){
                     gSecond.put(genres[i], gFirst.get(genres[i]));
                     gFirst.put(genres[i],music);
                     continue;
                 }
             }else{
                 gFirst.put(genres[i],music);
                 continue;
             }
            //장르별 2위 비교
            if(gSecond.containsKey(genres[i])){
                 if(gSecond.get(genres[i])[1] < plays[i]){
                     gSecond.put(genres[i],music);
                 }
             }else{
                 gSecond.put(genres[i],music);
             }
        }
        // 징르 정렬
        
        return answer;
    }
}

Python

import operator

def solution(genres, plays):
    gFirst = {} #장르별 1위
    gSecond = {} #장르별 2위
    gCount = {} #장르별 노래 수
    answer = []
    for i, genre in enumerate(genres) :
        
        # 장르별 노래 count
        if genre in gCount:
            gCount[genre] += plays[i]
        else:
            gCount[genre] = plays[i]
            
        if genre in gFirst:
            #현재 장르 1위와 비교
            if gFirst[genre][1] < plays[i] :
                gSecond[genre] = gFirst[genre]
                gFirst[genre] = [i, plays[i]]
                continue
        else:
            gFirst[genre] = [ i, plays[i]]
            continue
        
        if genre in gSecond:
            #현재장르 2위와 비교
            if gSecond[genre][1] < plays[i] :
                gSecond[genre] = [i, plays[i]]
        else:
            gSecond[genre] = [i, plays[i]]
    
    #노래많은 장르 정렬
    gSorted = sorted(gCount.items(), key=operator.itemgetter(1), reverse = True)
    for g in gSorted:
        answer.append(gFirst[g[0]][0])
        # 노래 1곡인지 check
        if g[0] in gSecond :
            answer.append(gSecond[g[0]][0])
    
    return answer