해시

프로그래머스 베스트 앨범 문제를 풀며 .. 해시 메서드를 외워야겠다고 다짐하였다.

🧠 해시(Hash)란?

• 데이터를 키(key) - 값(value) 쌍으로 저장하는 자료구조
• 빠르게 검색하고 추가/삭제할 수 있음 → 평균 시간복잡도 O(1)
• 충돌(collision)이 생기지 않는 이상 매우 빠름
• 대표 구조: HashMap, HashSet (자바)

---

☑️ 언제 사용하면 좋을까?

상황	설명
검색이 많은 경우	값이 있는지 빠르게 찾을 수 있음 (containsKey, contains)
빈도수 계산	어떤 값이 몇 번 등장했는지 빠르게 기록 가능
중복 제거	HashSet을 사용하면 중복된 값은 하나만 저장됨
(key → value) 매핑	ID → 이름, 단어 → 등장 횟수, 장르 → 노래 목록 등

---

🧩 HashMap<K, V> 주요 메서드와 예시

Map<String, Integer> map = new HashMap<>();

map.put("apple", 3);              // 값 추가 또는 수정
map.get("apple");                // 3 (키에 해당하는 값 반환)
map.containsKey("apple");        // true (키가 있는지 확인)
map.remove("apple");             // 키와 값 삭제
map.size();                      // 저장된 키 개수
map.isEmpty();                   // 맵이 비었는지 확인
map.keySet();                    // 모든 key 반환
map.values();                    // 모든 value 반환
map.getOrDefault("banana", 0);   // "banana" 키가 없으면 0 반환

예시: 단어 등장 횟수 세기

String[] words = {"apple", "banana", "apple", "apple", "banana"};
Map<String, Integer> countMap = new HashMap<>();

for (String word : words) {
    countMap.put(word, countMap.getOrDefault(word, 0) + 1);
}
System.out.println(countMap); // {apple=3, banana=2}

---

🧩 HashSet<T> 주요 메서드와 예시

Set<String> set = new HashSet<>();

set.add("apple");              // 값 추가
set.contains("apple");         // true (값 존재 여부)
set.remove("apple");           // 값 제거
set.size();                    // 원소 개수
set.isEmpty();                 // 비었는지 확인

예시: 중복 제거

String[] names = {"kim", "lee", "park", "kim", "lee"};
Set<String> uniqueNames = new HashSet<>();

for (String name : names) {
    uniqueNames.add(name);
}
System.out.println(uniqueNames); // [kim, lee, park] (중복 제거됨)

---

🧠 기타 팁

• TreeMap, LinkedHashMap도 있음
  • TreeMap: 정렬된 맵
  • LinkedHashMap: 입력 순서를 유지
• HashMap<String, List<>> 형태로도 많이 씀 → 특정 그룹에 대한 목록 관리에 유용

---

✅ 요약 표

자료구조	특징	주요 용도
HashMap<K,V>	키-값 쌍 저장	빠른 검색, 빈도수 저장
HashSet<T>	값만 저장 (중복 없음)	중복 제거, 빠른 포함 확인
TreeMap<K,V>	정렬된 키 저장	정렬 필요할 때
LinkedHashMap<K,V>	입력 순서 유지	순서 보존이 중요할 때

---

정답 스포 주의

import java.util.*;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // List<Music> musicList = new ArrayList<>();
        Map<String, Integer> genreTotal = new HashMap<>();
        Map<String, List<Music>> genreToMusic = new HashMap<>();
        
        for(int i=0;i<plays.length;i++){
            String genre = genres[i];
            int play = plays[i];
            Music music = new Music(genre,play, i);
            genreToMusic.putIfAbsent(genre,new ArrayList<>()); // 기존의 리스트가 없으면 리스트 초기화 해줘야함
            genreToMusic.get(genre).add(music);
            genreTotal.put(genre, genreTotal.getOrDefault(genre,0)+play);
        }
        
        List<String> sortedGenres = new ArrayList<>(genreTotal.keySet());
        sortedGenres.sort((a,b)-> genreTotal.get(b)-genreTotal.get(a));
        
        List<Integer> result = new ArrayList<>();
        
        for(String genre : sortedGenres){
            List<Music> musics = genreToMusic.get(genre);
            
            musics.sort((a,b)->{
                //재생수 우선으로 정렬하고 -> 인덱스로 정렬
                if(b.plays != a.plays) return b.plays-a.plays;
                return a.index-b.index;
            });
            
            for(int i=0; i<Math.min(2,musics.size());i++){
                result.add(musics.get(i).index);
            }
        }
        
        return result.stream().mapToInt(i->i).toArray();
        
        
        
    }
    
    class Music{
        String genre;
        int plays;
        int index;
        
        Music(String genre, int plays, int index){
            this.genre = genre;
            this.plays = plays;
            this.index = index;
        }
    }
    
}