99클럽 코테 스터디 2일차 TIL + 해시

이월(0216tw)·2024년 5월 21일

99클럽 TIL 개발자 취업 미들러 의상 자바 코딩테스트 코딩테스트준비 항해99

99클럽/알고리즘풀이

목록 보기

2/38

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42578 (프로그래머스)

학습 키워드

해시(HASH)

시도 방법

(1) 재귀사용 (실패)
(2) 반복문 + 수학적 지식 활용 (성공)

내가 작성한 코드

(1) 재귀 사용 (실패)

처음에는 재귀를 이용해 모든 경우 조합을 생성했지만 test1이 메모리 초과가 발생했다.

 //재귀 함수를 이용하여 의상 조합을 모두 계산한다. 
    public static List<List<Integer>> generateCombinations(Map<String, Integer> map) {
        List<List<Integer>> result = new ArrayList<>();
        
        generateCombinationsHelper(map, new ArrayList<>(map.keySet()), 0, new ArrayList<>(), result);
        return result;
    }

    // 재귀 함수
    private static void generateCombinationsHelper(Map<String, Integer> map, List<String> keys, int index,
                                                   List<Integer> currentCombination, List<List<Integer>> result) {
        if (index == keys.size()) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }

        String key = keys.get(index);
        
        // 현재 키를 포함하지 않는 경우 
        generateCombinationsHelper(map, keys, index + 1, currentCombination, result);
        
        // 현재 키를 포함하는 경우
        currentCombination.add(map.get(key));
        generateCombinationsHelper(map, keys, index + 1, currentCombination, result);
        currentCombination.remove(currentCombination.size() - 1);
    }

그래서 메모리를 많이 사용하지 않도록 반복문 등으로 로직을 변경해야 했다.

(2) 반복문 + 수학적 지식 활용 (성공)

import java.util.Map;
import java.util.HashMap; 
import java.util.List; 
import java.util.ArrayList; 
import java.util.Arrays;

class Solution {
    public int solution(String[][] clothes) {

        int answer = 1 ; 
        
        Map<String , Integer> map = makeHashMap(clothes); 
    
        for(int count : map.values()) {
            answer *= (count+1); 
        }
        return answer -1; 
    }
    
    
    //각 의상종류 별로 의상의 개수를 해시맵으로 저장한다. 
    public Map<String , Integer> makeHashMap(String[][] clothes) {     
        Map<String , Integer> map = new HashMap<>();          
        
        for(String[] cloth : clothes) {
            map.put(cloth[1] , map.getOrDefault(cloth[1] , 0) + 1); 
        }        
        return map; 
    }      
}

[케이스 설명]

주어진 예시

[["yellow_hat", "headgear"],
["blue_sunglasses", "eyewear"],
["green_turban", "headgear"]]
과 같은 케이스를 일단 map으로 정리한다. {의상종류 : 의상개수}

map 정리 결과

{ "headgear" : 2 , "eyewear" : 1 }

그리고 나서 조합 가능한 경우의 수를 수학적으로 계산한다.

위 코드의 for문을 순서대로 보면 map.values() 를 통해
위 values 들이 [2,1] 로 출력이 된다.

이를 (count+1) 한 값을 answer에 곱하고 있다.
count + 1인 이유는 해당 의상을 선택하지 않은 경우를 포함한다.

예)

answer (3) = (2 + 1) //헤드기어 경우2가지 + 헤드기어 안하는 경우1가지
answer (6) = (1 + 1) //안경 경우 1가지 + 안경 안하는 경우 1가지

이는 아래와 같은 의미이다.

헤드1 (헤드기어 경우 + 안경을 안 한 경우)
헤드2 (헤드기어 경우 + 안경을 안 한 경우)
안경1 (안경 경우 + 헤드기어 안 한 경우)

헤드1 + 안경1 (헤드기어 경우 + 안경을 한 경우)
헤드2 + 안경1 (헤드기어 경우 + 안경을 한 경우)

x (헤드기어 안 한경우 + 안경을 안 한 경우)

테스트 결과

새롭게 알게된 점

해시맵을 사용할 때 getOrDefault 방법을 이용하면 코드 수를 줄일 수 있고 가독성을 높일 수 있었다. (예전에는 if(map.get(key) == null) { } else { .. } 처럼 작성했음)
코드 풀이에 수학적 지식도 함양해야 겠다는 것을 깨달았다.
처음에 재귀로 풀때도 가능은 했지만 메모리 초과가 났던 게 너무 아쉬웠다.
하지만 수학적인 배경을 가지고 있다면 보다 빠르게 문제를 해결할 수 있다는 점이 또 매력적으로 느껴진다