[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;
​​​​}
}