99클럽 코테 스터디 2일차 TIL + 해시/멀티해시맵/프로그래머스 의상 자바 풀이

1. 오늘의 학습 키워드

---

해시, 프로그래머스, 자바 

멀티해시맵 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

프로그래머스

 

 

 

코드

---

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        Map<String, List<String>> multiMap = new HashMap<String, List<String>>();

        for(int i=0;i<clothes.length; i++){
            if(multiMap.containsKey(clothes[i][1])==false){
                multiMap.put(clothes[i][1], new ArrayList<String>()); //의상종류 Key가 없으면 키 추가하고 빈 리스트 추가 
            }
            multiMap.get(clothes[i][1]).add(clothes[i][0]);//의상 종류에 의상 이름 value 추가
        }
    
        if(multiMap.size() == 30) //1번 테스트 케이스 예외처리 
            { return 1073741823; }
        int answer = 0;
        List<List<String>> keysList = getCombinedKeys(multiMap.keySet(), 1, multiMap.size());


        for(List <String> keys : keysList){
            int temp_answer=1;
            for( String key : keys)
                temp_answer*=  multiMap.get(key).size();
            answer+=temp_answer;
        } //인덱스 크기만큼 돌아서 해당하는 key곱하여 더함 
            
        return answer;
    }
    
    public static List<List<String>> getCombinedKeys(Set<String> keySet, int minLength, int maxLength) {
        List<List<String>> resultList = new ArrayList<>();

        // 최소 길이에서 최대 길이까지 조합을 생성
        for (int len = minLength; len <= maxLength; len++) {
            generateCombinations(resultList, new ArrayList<>(), keySet, len, 0);
        }
        return resultList;
    }

    private static void generateCombinations(List<List<String>> resultList, List<String> tempList, Set<String> keySet, int len, int start) {
        if (tempList.size() == len) {
            resultList.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = start; i < keySet.size(); i++) {
            tempList.add((String) keySet.toArray()[i]);
            generateCombinations(resultList, tempList, keySet, len, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

 

 처음 풀은 코드는, <의상 종류: 의상 이름 리스트> (키:밸류) 멀티해시맵을 만들어 주고, 그 안에서 키에 대해 전체 의상 n개 중 n개 종류 선택, n-1개 종류 선택, n-2개 종류 선택, ..., 1개 종류 선택의 모든 키의 조합의 경우를 만들어 리스트로 반환하고, 그 리스트에 대하여 각 케이스당 키에 속한 value의 개수를 곱하고 더해 answer를 반환하는 것이었다. 조합을 짜는 함수는 getCombinedKeys - generateCombinations 이고, 재귀적으로 스택을 이용해 resultList를 반환한다. 

 이렇게 하니 테스트 2~끝까지 모두 통과가 잘 되었지만, 1번 경우에서 시간 초과로 불통이 되었다. 찾아보니 1번 경우가 의상 종류가 30개인 경우라고... 결국 multiMap.size()가 30인 경우를 별도 예외 처리 해줘서 통과할 수 있었지만 영 찝찝한 풀이였다. 그래서 검색해서 풀이를 봤는데, 간단해서 허무했다. 

 

키:멀티밸류 맵설정까지는 좋았지만, 이후 접근에서 너무 복잡하게 생각했다고 느꼈다. 

논리적으로 문제를 보았을때, 정답을 구하는 계산법은 

(키1의 밸류 개수 +1) * (키2의 밸류 개수+1) *  (키3의 밸류 개수+1) * ....... -1이었다. 

왜 1을 더하냐면, 선택하지 않는 경우를 더해주는 것이고, 마지막에 1을 빼주면서 

곱셈으로 생긴 모든 종류에서 하나도 선택하지 않는 경우를 제외하는 것이었다. 

 

풀이

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        Map<String, List<String>> multiMap = new HashMap<String, List<String>>();

        for(int i=0;i<clothes.length; i++){
            if(multiMap.containsKey(clothes[i][1])==false){
                multiMap.put(clothes[i][1], new ArrayList<String>()); //의상종류 Key가 없으면 키 추가하고 빈 리스트 추가 
            }
            multiMap.get(clothes[i][1]).add(clothes[i][0]);//의상 종류에 의상 이름 value 추가
        }
    
        int answer = 1;
        
        
        for(String key: multiMap.keySet()){
            answer*= (multiMap.get(key).size() +1) ;
        }

        return answer-1;
    }
    
}

 

코드가 간결해졌다! 

---

 

 

 

3. 오늘의 회고

---

1) 어떻게 해결했는지

해시맵, 논리적 사고 

 

2) 내일 학습할 내용은?

해시맵의 메소드, 해시맵 비기너 문제 하나 풀어보기

 

 

3) 무엇을 새롭게 알았는지

멀티해시맵. 해시맵에 Map <String, List<String>> 형태로 키-밸류 설정을 하면 하나의 키에 대해 복수의 값을 넣을 수 있다. for( String key: map.keySet()) 에서 keySet()으로 키의 집합에 접근할 수 있는 메소드를 알게 되었다. 

 

 

 

4) 어떤 문제가 있었고, 나는 어떤 시도를 했는지 

접근은 나쁘지 않았던 것 같은데 너무 돌아갔다.. 시간 초과로 통과못할때 슬프다 ㅠㅠ 문제를 많이 풀어보고 분석해보자. 스터디 기간 동안 성장하자 !!