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

https://programmers.co.kr/learn/courses/30/lessons/42579

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

풀이법:

두 가지 리스트를 만들어서 푼다: 1) HashMap <장르, 장르의 총 플레이 횟수> 2) PriorityQueue<곡 번호, 플레이횟수>

1)은 만들고 플레이 횟수에 따라 내림차 순으로 정렬한다.

2)는 장르의 개수만큼 만든다. <곡 번호, 플레이횟수>는 개념적으로 설명을 위해 표기한 것이고 구현할 때는 no, count를 변수로 가진 클래스를 새롭게 정의함(El)

그리고 Comparable 인터페이스를 implement해서 count크기에 따라 PriorityQueue에 저장한다.

 

모든 2) 리스트에서 poll()을 두번 씩 하면 답 나옴.

 

Comment:

1) Hash의 중요성: <종류, 출현횟수> 형식의 자료구조를 저장하는 경우는 꽤 자주 접하는 상황이다. 이를 구현하는 가장 좋은 자료구조는 hash. 그냥 배열로 하면 n제곱 이지만 hash로 하면 n이기 때문.

2) 알고리즘 문제라기 보다 자료구조 잘 쓸줄 아냐 물어보는거 같은 문제.. 이게 왜 level3이지? 

3) 너무 더럽게 푸는거 같음

import java.util.*;

public class El implements Comparable<El>{
	int no;
	int count;
    
	public El(int no, int count) {
		super();
		this.no = no;
		this.count = count;
	}
    
	@Override
	public int compareTo(El el) {
		if(this.count > el.count) {
			return 1;
		}else if(this.count < el.count) {
			return -1;
		}
		return 0;
	}
}
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap <String, Integer> total = new HashMap();
		for(int i = 0; i < genres.length; i++) {
			if(total.containsKey(genres[i])) {
				total.replace(genres[i], total.get(genres[i]) + plays[i]);
			}else {
				total.put(genres[i], plays[i]);
			}	
		}
		
		Iterator iter = sortByValue(total).iterator(); //collection의 sort는 nlogn, n = 100
	
		ArrayList<PriorityQueue> list = new ArrayList();
		
		while(iter.hasNext()) {
			String temp = (String) iter.next();
			//System.out.println(temp + " = " + total.get(temp));
			PriorityQueue <El> pq = new PriorityQueue<El>(Collections.reverseOrder());
			for(int i = 0; i < genres.length;i++) {
				if(temp.contentEquals(genres[i])) {
					El e = new El(i, plays[i]);
					pq.add(e);
				}
			}
			list.add(pq);
		}
		
		
		ArrayList<Integer> ans = new ArrayList();
		
		for(int i = 0; i < list.size(); i++) {
			PriorityQueue<El> temp = list.get(i);
			int count = 0;
			while(!temp.isEmpty()) {
				if(count == 2) break;
				else {
					ans.add(temp.poll().no);
					count++;
				}
			}
		}
		
		System.out.println(ans);
		
		int[] answer = new int[ans.size()];
		int size = 0;
		for(int temp : ans) {
			answer[size++] = temp;
		}
    
        return answer;
    }
    
    	public static List sortByValue(final Map map) {
		List<String> list = new ArrayList();
		list.addAll(map.keySet());
		Collections.sort(list,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 list;
		}
    
}