[Java][Programmers][고득점 Kit ] Hash (완주하지 못한 선수, 전화번호 목록, 위장, 베스트앨범)

프로그래머스 고득점 Kit에 있는 해시 문제는 총 4개이다. 

 

모두 key - value 쌍을 활용하면 풀기 쉬워지는데 자주 사용하는 것은 Collections을 이용한 sort , getOrDefault를 이용한 값 추가이다. 

 

 

 

---

완주하지 못한 선수 (Level1) 

- getOrDefault만 잘 사용하면 쉽게 풀리는 문제. 

 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

 

---

전화번호 목록 (Level2)

- Comparator를 활용해서 길이순으로 먼저 내림차순 정렬 해준다. 내림차순으로 정렬한 이유는 긴 것이 짧은 것의 prefix가 될 수 없기 때문이다. 

 

- 만약 "1195524421"이 있으면 "1195524421"은 확인하고자 하는 hashMap에는 존재하지 않는다. (존재하면 prefix니까 종료)
  그 후에 "1", "11", "119" , "1195" ...."1195524421" 까지의 값들이 prefix를 확인해야 하는 hashMap으로 넘어간다.

  그 다음 짧은 값으로 차례대로 비교

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
       Arrays.sort(phone_book, new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });

        HashMap<String, Integer> hm = new HashMap<>();
        for (String str : phone_book) {
            
            if (hm.get(str) != null) {
                return false;
            }
            for (int i = 1, len = str.length() ; i <= len; i++) {
                hm.put(str.substring(0, i), 1);
            }
        };
        return true;
    }
}

 

---

위장 (level2)

- https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

 

- 경우의 수를 생각해주면 된다. 얼굴 2개, 하의 2개면 (얼1,얼2,착X)*(하1,하2,착X) 만큼의 경우의 수가 생긴다.

 이때, 주의해야 할 점은 모든 옷을 벗을 수는 없으므로 모든 경우의 수에서 1개를 빼줘야 한다. (모두 벗는 경우 제외)

 

- 약간의 아이디어와 getOrDefault를 활용하면 된다. 

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        HashMap<String,Integer> map=new HashMap<String,Integer>();
        
        for(int i=0;i<clothes.length;i++){
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);
        }
        
        for(String key: map.keySet()){
            answer*=map.get(key)+1;
        }
        
        return answer-1; // 아무것도 안입는 경우는 없으니까 1 제외 
    }
}

 

---

베스트앨범 (level3)

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

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

- hashMap을 value 내림차순으로 정렬하는 방법, class Node를 정렬하는 방법 두가지를 사용해야 한다.

- 먼저 장르순으로 내림차순 해야되기에 getOrDefault로 값들을 넣어주고 keySet을 사용해 List를 내림차순 정렬해준다. 

- 모든 Music을 넣어준 뒤에 재생 횟수순으로 정렬해준다. (재생 횟수가 같으면 고유번호가 낮은 순으로)

  그 뒤에 key를 확인하면서 2개를 찾아내면 다음 Key로 이동하는 방식이면 된다. 

   모든 경우를 찾을 수도 있지만 총 10000개, 장르가 100개니까 최악의 경우 100만.. 시간 효율은 좋지 않다.

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int len=genres.length; 
        Music[] music=new Music[len];
        HashMap<String,Integer> map=new HashMap<String,Integer>();
        
        for(int i=0;i<genres.length;i++){
            map.put(genres[i],map.getOrDefault(genres[i],0)+plays[i]);
            music[i]=new Music(genres[i],plays[i],i);
        }
        Arrays.sort(music);
        List<String> keyList=new ArrayList<>(map.keySet());
        Collections.sort(keyList,(o1,o2) -> (map.get(o2).compareTo(map.get(o1))));
        
        List<Integer> list=new ArrayList<Integer>();
        for(String key: keyList){
            int cnt=0;
            for(int i=0;i<genres.length;i++){
                if(music[i].gerne.equals(key)){
                    list.add(music[i].id);
                    cnt++;
                    if(cnt==2)
                        break;
                }
            }
        }
        
        int[] answer=new int[list.size()];
        for(int i=0;i<list.size();i++){
            answer[i]=list.get(i);
        }
        
        
        return answer;
    }
    static class Music implements Comparable<Music>{
        String gerne;
        int cnt,id;
        
        public Music(String gerne,int cnt,int id){
            this.gerne=gerne;
            this.cnt=cnt;
            this.id=id;
        }
        
        public int compareTo(Music o){
            int diff=o.cnt-this.cnt;
            if(diff==0)
                diff=this.id-o.id;
            return diff;
        }
    }
}