[코테 준비 : day14] 해시

1. 폰켓몬

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

[문제 풀이 고민]
n/2의 폰켓몬을 가져갈 수 있는 상황.
(출력) 가장 많은 포켓몬의 종류를 선택할 수 있는 종류의 수를 리턴하면 됨

1. 먼저 배열에 중복된 부분들을 모두 삭제 한다.

• Stream API를 사용하여 중복되지 않은 새 어레이을 만드는 것
  배열 -> Stream -> distinct (중복제거) -> 배열

 Arrays.stream(arr).distinct().toArray();

2. 조건문으로 카운트를 확인한다.

• 만약 중복을 제거한 배열의 수와 뽑아야하는 수가 같다면 최대 종류는 '배열의 수'
• 중복을 제거한 배열의 수보다 뽑아야하는 수가 작다면 최대 종류의 수는 '뽑아야하는 수'

[최종 코드]

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        //선택 가능 갯수
        int choose = nums.length / 2;
        //중복 제거
        int[] numStr = Arrays.stream(nums).distinct().toArray();

        if(numStr.length > choose)
            answer = choose;
        
        else
            answer = numStr.length;

        
        return answer;
    }
}

[해시를 이용한 풀이]

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        //배열의 길이의 절반
        int maxNums = nums.length / 2;
        int setSize = set.size();
        return setSize > maxNums ? maxNums : setSize;
    }
}

---

2. 완주하지 못한 선수

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

[문제 풀이 고민]

(출력) 완주하지 못한 선수의 이름을 리턴

1. 해시맵에 참가한 선수들을 입력,key는 선수들의 이름 value는 1로 만듬
2. 중복 되는 선수는 value에서 + 1을 시켜서 1명이 더 있다는 것을 입력
3. 참가한 선수들 중 완주한 선수는 value를 -1로 넣음
   만약 완주한 선수하라면 value는 0이 됨
4. 해시맵에서 완주하지 못한 선수인 value가 1인 선수를 찾음

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> set = new HashMap<>();

        for(int i = 0; i < participant.length; i++){
            String name = participant[i];
            if (set.containsKey(name)) {
                set.put(name, set.get(name) + 1);
            } 
            else {
                set.put(name, 1);
            }
        }
        
        for(int i = 0; i < completion.length; i++){
            String name = completion[i];
            set.put(name, set.get(name) - 1);
        }
        
        //완주하지 못한 선수
        for(String key : set.keySet()){
            int value = set.get(key);
            if(value == 1){
                answer = key;
                break;
            }
        }

   
        return answer;
    }
}

[다른 사람 참고 코드]

import java.util.HashMap;

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;
    }
}

---

3. 전화번호 목록

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

[문제 풀이 고민]

(출력) 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 리턴

1. 먼저 전화번호를 재정렬
2. 인수로 지정한 문자열로 시작하는 경우 True값을 반환하며, 그렇지 않다면 False 값을 반환(startwith 사용)
   참고 함수 : https://wookoa.tistory.com/151

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book); //전화번호 정렬
        
        for(int i = 0; i < phone_book.length - 1; i++){
            if(phone_book[i + 1].startsWith(phone_book[i]))
                answer = false;
        }


        return answer;
    }
}

[해시 사용 풀이]

• containsKey(key) : 주어진 key가 HashMap에 존재하는지 여부를 반환합니다. 존재하면 true를 출력

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Map<String, Integer> map = new HashMap<>();

        // 해시에 모든 전화번호를 저장합니다.
        for (String number : phone_book) {
            map.put(number, 0);
        }

        // 모든 전화번호를 순회하면서, 해당 전화번호의 부분 문자열이 해시에 있는지 확인합니다.
        for (String number : phone_book) {
            for (int i = 1; i < number.length(); i++) {
                if (map.containsKey(number.substring(0, i))) {
                    answer = false;
                    return answer;
                }
            }
        }

        return answer;
    }
}

---

4. 의상

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

[문제 풀이 고민]

(출력) 서로 다른 옷의 조합 수를 리턴
최소 1개 이상의 의상을 입어야함

1. 해시맵에 각각의 옷들을 넣는다. ( 옷의 종류, 개수)
   옷 종류를 cloth[1]로 표현
2. getOrDefault() 메소드를 사용하여 해당 종류를 키로 하는 값이 존재하면 그 값을 가져옴. 만약 없으면 0을 있으면 그 값에 + 1을 함
3. 각 종류별 개수에 + 1,1을 더한 이유는 해당 종류의 옷을 입지 않는 경우도 고려하기 위함
4. 모든 종류를 입지 않는 경우가 포함이 되므로 마지막에 -1

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map <String,Integer> map = new HashMap<>();

        for(String[] cloth : clothes){
            //옷 종류가 같으면 + 1
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }

        for(Integer count : map.values()){
            answer *= (count + 1);
        }

        return answer - 1;
    }
}

[다른 사람 코드 참고]

import java.util.HashMap;
import java.util.Iterator;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();
        for(int i=0; i<clothes.length; i++){
            String key = clothes[i][1];
            if(!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                map.put(key, map.get(key) + 1);
            }
        }
        Iterator<Integer> it = map.values().iterator();
        while(it.hasNext()) {
            answer *= it.next().intValue()+1;
        }
        return answer-1;
    }
}

---

5. 베스트앨범

한번더 확인하고 풀어야할듯. 정렬부분을 많이 찾아본거라 아직 내 것이 되지 않음

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

[문제 풀이 고민]

(출력) 베스트 앨범에 들어갈 노래의 고유 번호 순서대로 리턴

1. 노래별 재생 횟수를 저장
2. 장르별로 분류된 리스트에 고유 번호 추가
3. 장르별 총 재생 횟수를 기준으로 내림차순 정렬
4. 각 장르별 노래 리스트를 뽑아서 해당 리스트를 정렬
5. 베스트 앨범에 들어갈 노래의 고유 번호를 리스트에 추가

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};

        //장르별로 분류
        Map <String,List<Integer>> map = new HashMap<>();
        //노래별 재생 횟수
        Map<String, Integer> genrePlayCountMap = new HashMap<>();

        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int playCount = plays[i];
            int songIndex = i;
            
            // 노래별 재생 횟수를 저장
            genrePlayCountMap.put(genre, genrePlayCountMap.getOrDefault(genre, 0) + playCount);
            
            //장르별로 분류된 리스트에 고유 번호 추가
            if (!map.containsKey(genre)) {
                map.put(genre, new ArrayList<>());
            }

            map.get(genre).add(songIndex);
        }

        //장르별 총 재생 횟수를 기준으로 내림차순 정렬
        List<Map.Entry<String, Integer>> genrePlayCountList
         = new ArrayList<>(genrePlayCountMap.entrySet());
        Collections.sort(genrePlayCountList, (a, b) -> b.getValue() - a.getValue());

        //각 장르별 노래 리스트를 뽑아서 해당 리스트를 정렬
        for (Map.Entry<String, Integer> entry : genrePlayCountList) {
            String genre = entry.getKey();
            List<Integer> songList = map.get(genre);
            Collections.sort(songList, (a, b) -> {
                if (plays[a] == plays[b]) {
                    return a - b;
                }
                return plays[b] - plays[a];
            });
        }

        //베스트 앨범에 들어갈 노래의 고유 번호를 리스트에 추가
        List<Integer> resultList = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : genrePlayCountList) {
            String genre = entry.getKey();
            List<Integer> songList = map.get(genre);
            int count = 0;
            for (int song : songList) {
                if (count == 2) {
                    break;
                }
                resultList.add(song);
                count++;
            }
        }

        //리스트를 배열로 변환하고 반환

        answer = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            answer[i] = resultList.get(i);
        }
        return answer;
        
    }
}