[JAVA] 해시 "베스트앨범"

내가 작성한 코드 : 시간초과.

import static java.util.stream.Collectors.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CodingTestExample이니까다하고삭제 {
    public static int findMaxMusic(String[] genres, int[] plays , String max_key){
        int maxOftheGenre = 0;
        int maxi = 0;
        for(int i = 0; i<genres.length; i++){
            if(genres[i].equals(max_key) && plays[i] > maxOftheGenre){
                maxOftheGenre = plays[i];
                maxi = i;
            }
        }

        return maxi;
    }

    public int[] solution(String[] genres, int[] plays) {

        HashMap<String, Integer> hm = new HashMap<>();

        for(int i = 0; i<genres.length; i++){
            hm.put(genres[i], hm.getOrDefault(genres[i], 0) + plays[i]);
        }
        int max =0;
        String max_key = "";
        for(String key : hm.keySet()){
            if(hm.get(key) > max) {//value 비교
                max = hm.get(key);
                max_key = key;
            }
        }
        int firstPlays = findMaxMusic(genres, plays, max_key);

        plays[firstPlays] = 0; // 가장 큰 값 제거

        int secondPlays = findMaxMusic(genres, plays, max_key);

        System.out.println(firstPlays + " and " + secondPlays);

        //두번째값
        hm.remove(max_key);

        max =0;
        max_key = "";
        for(String key : hm.keySet()){
            if(hm.get(key) > max) {//value 비교
                max = hm.get(key);
                max_key = key;
            }
        }
        int thirdPlays = findMaxMusic(genres, plays, max_key);

        plays[thirdPlays] = 0; // 가장 큰 값 제거

        int forthplays = findMaxMusic(genres, plays, max_key);

        int[] answer = {firstPlays, secondPlays, thirdPlays, forthplays};



        return answer;
    }

}

 

스트림으로 작성한 코드(다른 분의 풀이)

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
  public class Music implements Comparable<Music>{

    private int played;
    private int id;
    private String genre;

    public Music(String genre, int played, int id) {
      this.genre = genre; 
      this.played = played;
      this.id = id;
    }

    @Override
    public int compareTo(Music other) {
      if(this.played == other.played) return this.id - other.id;
      return other.played - this.played;
    }

    public String getGenre() {return genre;}
  }

  public int[] solution(String[] genres, int[] plays) {
    return IntStream.range(0, genres.length)
    .mapToObj(i -> new Music(genres[i], plays[i], i))
    .collect(Collectors.groupingBy(Music::getGenre))
    .entrySet().stream()
    .sorted((a, b) -> sum(b.getValue()) - sum(a.getValue()))
    .flatMap(x->x.getValue().stream().sorted().limit(2))
    .mapToInt(x->x.id).toArray();
  }

  private int sum(List<Music> value) {
    int answer = 0;
    for (Music music : value) {
      answer+=music.played;
    }
    return answer;
  }
}

 

 

댓글에 의하면 다른 모범풀이의 코드들보다 10배정도 더 오래 시간이 소요된다고 한다.

스트림 장인기법이니 스트림 사용 참고용으로 볼 것.

 

다음은 해쉬 형변환을 이용한 것. 좀 연구할 필요가 있다.

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Collections;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Object> genresMap = new HashMap<String, Object>();      //<장르, 곡 정보> 
        HashMap<String, Integer> playMap = new HashMap<String, Integer>(); //<장르, 총 장르 재생수>
        ArrayList<Integer> resultAL = new ArrayList<Integer>();

        for(int i = 0; i < genres.length; i++){
            String key = genres[i];
            HashMap<Integer, Integer> infoMap;       // 곡 정보 : <곡 고유번호, 재생횟수>

            if(genresMap.containsKey(key)){
                 infoMap = (HashMap<Integer, Integer>)genresMap.get(key);
            }
            else {
                infoMap = new HashMap<Integer, Integer>();
            }

            infoMap.put(i, plays[i]);
            genresMap.put(key, infoMap);

            //재생수
            if(playMap.containsKey(key)){
                playMap.put(key, playMap.get(key) + plays[i]);
            }
            else {
                playMap.put(key, plays[i]);
            }
        }

        int mCnt = 0;
        Iterator it = sortByValue(playMap).iterator();

        while(it.hasNext()){
            String key = (String)it.next();
            Iterator indexIt = sortByValue((HashMap<Integer, Integer>)genresMap.get(key)).iterator();
            int playsCnt = 0;

            while(indexIt.hasNext()){
                resultAL.add((int)indexIt.next());
                mCnt++;
                playsCnt++;
                if(playsCnt > 1) break;
            }
        }

        int[] answer = new int[resultAL.size()];

        for(int i = 0; i < resultAL.size(); i++){
            answer[i] = resultAL.get(i).intValue();
        }

        return answer;
    }

    private ArrayList sortByValue(final Map map){
        ArrayList<Object> keyList = new ArrayList();
        keyList.addAll(map.keySet());

        Collections.sort(keyList, new Comparator(){
            public int compare(Object o1, Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);

                return ((Comparable) v2).compareTo(v1);
            }
        });

        return keyList;
    }
}