[프로그래머스 level3] - 베스트앨범 (Java), 해시(hash)에 대한 모든 것(코딩테스트를 위한 해시, CS를 위한 해시)

 

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

프로그래머스

 

풀이 방법

1. 장르별 재생 횟수 저장
2. 각 장르에 속한 노래의 <고유번호, 재생 횟수> 저장
3. 장르별 재생 횟수를 저장
4. 곡 수대로 내림차순 정렬
5. 정렬된 num의 순서대로 상위 2곡의 고유번호를 ArrayList에 저장

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> num = new HashMap<>();
        HashMap<String, HashMap<Integer, Integer>> music = new HashMap<>();
        
        for(int i=0; i<plays.length; i++) {
            if(!num.containsKey(genres[i])) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(i, plays[i]);
                music.put(genres[i], map);
                num.put(genres[i], plays[i]);
            } else {
                music.get(genres[i]).put(i, plays[i]);
                num.put(genres[i], num.get(genres[i]) + plays[i]);
            }
        }
        
        List<String> keySet = new ArrayList(num.keySet());
        Collections.sort(keySet, (s1, s2) -> num.get(s2) - (num.get(s1)));
        
        for(String key : keySet) {
            HashMap<Integer, Integer> map = music.get(key);
            List<Integer> genre_key = new ArrayList(map.keySet());
            
            Collections.sort(genre_key, (s1, s2) -> map.get(s2) - (map.get(s1)));
            
            answer.add(genre_key.get(0));
            if(genre_key.size() > 1) {
                answer.add(genre_key.get(1));
            }
        }
        
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

 

 

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

classic	pop
500 + 150 + 1800	600 + 2500

1. num에 장르별 재생 횟수를 저장합니다.

 

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

classic	pop
0      2     3	1        4
500 150   800	600  2500

2. 각 장르에 속한 노래의 고유번호, 재생 횟수를 저장합니다.

 

3. 장르별 재생 횟수를 저장

pop	classic
3100	1450

 

4. 장르별 총 재생 횟수 정렬

List<String> keySet = new ArrayList(num.keySet());
Collections.sort(keySet, (s1, s2) -> num.get(s2) - (num.get(s1)));

 

5. 장르별 노래 정렬

for(String key : keySet) {
    HashMap<Integer, Integer> map = music.get(key);
    List<Integer> genre_key = new ArrayList(map.keySet());
            
    Collections.sort(genre_key, (s1, s2) -> map.get(s2) - (map.get(s1)));
            
    answer.add(genre_key.get(0));
    if(genre_key.size() > 1) {
        answer.add(genre_key.get(1));
    }
 }

 

 

코딩테스트를 위한 해시 자료구조 

-----------------------------------------------------------------------------------------------------------------------------------

해시(Hash)

Key:Value의 구조를 갖는 자료구조

HashMap

• key는 중복 허용하지 않는다. (value는 가능) 중복된 값이 들어오면 덮어씌워짐
• 데이터 순서 없음
• put() : 데이터 삽입
• get(키값) : key의 value얻기
• getOrDefault(a, b) : a가 없으면 b를 출력, 있으면 value 값 출력
• remove(키값) : 해당 데이터 삭제
• containsKey(키값) : 해당 키가 존재하는지 여부 (boolean return)
• clear() : 전체 요소 삭제
• keySet() : 맵에 저장된 모든 키들을 Set 형태로 반환

HashSet

• 중복을 허용하지 않는 집합
• 데이터 순서 없음
• add() : 데이터 삽입
• contains() : 해당 원소 포함 여부(boolean return)

 

해시 테이블, 해시 함수, 해시 충돌, 해싱에 대한 설명

https://github.com/AnChanUng/TIL/blob/main/algorithm/hash.md