해시란?

Key-value쌍으로 데이터를 저장하는 자료구조

🚀주요 사용하는 기능 in JAVA

HashMap<K, V> map

타 언어의 Dictionaray와 같은 역할을 하는 자료구조.
가장 중요한 점은 역시 기적적인 Hash의 성능을 통해 저장된 Key에 해당하는 Value를 O(1)의 시간복잡도로 검색이 가능하다는 것.
(충돌 및 재해시를 통한 효율감소에 대한 얘긴 여기선 생략하도록 하자)

HashMap.replace(K, V)

자바의 HashMap의 요소에 대한 수정은 생각보다 복잡하다. 귀찮지만 이렇게 replace()와 get()을 통해 접근, 수정해주도록 하자
말할 필요도 없이 시간복잡도는 상수시간이다.

HashMap.containsKey(K), HashMap.containsValue(V)

이름처럼 해당 Map에 Key나 Value의 포함을 확인하는 함수.
주로 containsKey()를 통해 Key가 있는지 확인하고 없을 시에 put()해주는 식으로 사용한다.

HashMap.keySet(), HashMap.values()

Key와 Value를 모아놓은 자료구조를 각각 반환하는 메서드.
짚고 넘어갈 점은, keySet()의 경우 Set<K>형태를 반환하지만 values()는 Collections<V>와 같은 좀 불편한 형태를 반환한다는 것.
주로 KeySet()을 통해 반환된 Set으로 Map의 요소를 순환하고 싶을 때 사용된다.

---

완주하지 못한 선수 (Level 1)

가장 기초적인 문제.
보이는 난이도처럼 단지 HashMap에 값을 넣고 찾는 것만으로 끝인 문제다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        for(String p : participant){
            if(map.containsKey(p)){
                map.replace(p, map.get(p)+1);
            }else{
                map.put(p, 1);
            }
        }
        
        for(String c : completion){
            map.replace(c, map.get(c)-1);
        }
        String answer = "";
        for(String s : map.keySet()){
            if(map.get(s)==1){
                answer = s;
                break;
            }
        }
        return answer;
    }
}

전화번호 목록 (Level 2)

너무 쓸데없이 어렵게 푼게 아닌가 싶은 문제 1
자바에는 내가 알기로 Swift의 extension이나 Javascript의 ProtoType과 같이 기존의 클래스를 재정의 할 수 있는 방법이 없기 때문에 Comparator라는 조금 생소한 클래스를 생성하여 String의 길이로 정렬하여 풀었다.
다 풀고 다른사람의 풀이를 보며 뒤늦게 깨달은 점은 접두사의 포함관계를 위한 정렬에 있어선, 굳이 문자열 길이에 대한 정렬이 필요 없다는 것........💦(그냥 Sort해도 된다..)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {

        boolean answer = true;

        Arrays.sort(phone_book, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                return o2.length() - o1.length();
            }
        });


        HashMap<String, Boolean> map = new HashMap<>();

        for(String str : phone_book){
            if(map.containsKey(str)){
                answer = false;
                break;
            }
            for(int i  = 1 ; i < str.length() ; i++){
                String sub = str.substring(0, i);
                if(!map.containsKey(sub)){
                    map.put(sub, true);
                }
            }
        }

        return answer;


    }
}

위장(Level 2)

Hash문제라기 보단, 기초적인 경우의 수 문제에 가깝다고 생각했다. 예를들어

2^3 * 3^2 * 5*2의 약수의 개수는?

이런느낌?

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        int answer = 1;
        for(int i=0 ; i<clothes.length ; i++){
            String key = clothes[i][1];
            if(!map.containsKey(key)){
                map.put(key, 1);
            }else{
                map.replace(key, map.get(key)+1);
            }
        }
        for(String key : map.keySet()){
            answer*=map.get(key)+1;
        }
        return answer-1;
    }
}

베스트 앨범(Level 3☠️)

프로그래머스에서 처음 풀어본 레벨 3문제.
(그런데 막상 레벨을 안보고 풀다가, 생각보다 복잡해서 짜증났다)

장르와 노래에 대한 Sort가 모두 필요하기 때문에, 각각의 구조에 대한 포함관계를 설계하는게 살짝 까다로운 문제다.

그리고 개인적으로 HashMap.values와 toArray()에 대한 타입변환 때문에 상당히 애먹었다.

대부분의 문제가 그렇겠지만, 특히 이러한 설계문제의 경우, 무작정 풀기 시작하는 것 보단 노트나 메모장에 전체적인 흐름이나 스켈레톤 코드를 미리 짜 보고 시작하는게 훨씬 접근하기 좋을 것 같다.

import java.util.*;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Song[] songs = new Song[genres.length];
        HashMap<String, Genre> map = new HashMap<>();
        for(int i=0 ; i<genres.length ; i++){
            String genName = genres[i];
            int play = plays[i];
            Song s = new Song(i, play);
            if(!map.containsKey(genName)){
                map.put(genName, new Genre(genName));
            }
                Genre genre = map.get(genName);
                genre.songs.add(s);
                genre.total += play;
        }
        Object[] tmp = map.values().toArray();
        Genre[] gs = new Genre[tmp.length];

        for(int i=0 ; i<tmp.length ; i++){
            gs[i] = (Genre)tmp[i];
        }
         
        Arrays.sort(gs);
        ArrayList<Integer> ans = new ArrayList<>();
        
        for(Genre gg : gs){
            ArrayList<Song> ss = gg.songs;
            Collections.sort(ss);
            for(int i=0 ; i<(2 < ss.size() ? 2 : ss.size()); i++){
                ans.add(ss.get(i).idx);
            }
        }
        
        Object[] aa = ans.toArray();
        int[] bb = new int[aa.length];
        for(int i=0 ; i<aa.length ; i++) {
        	bb[i] = (int)aa[i];
        }
        return bb;
    }
}
class Genre implements Comparable<Genre>{
    int total;
    String name;
    ArrayList<Song> songs;
    Genre(String name){
        this.name = name;
        songs = new ArrayList();
        this.total = 0;
    }
    @Override
    public int compareTo(Genre o){
        return o.total - this.total;
    }
}
class Song implements Comparable<Song>{
    int idx;
    int play;
    Song(int idx, int play){
        this.idx = idx;
        this.play = play;
    }
    @Override
    public int compareTo(Song o){
        if(this.play == o.play){
            return this.idx - o.idx;
        }else{
            return o.play - this.play;
        }
    }
}