해시(Hash)를 활용한 알고리즘 문제풀이

오늘 푼 문제: 의상

• 입력: 코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어집니다.
• 출력: 서로 다른 옷의 조합의 수를 return 합니다.

예제 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < clothes.length; i++) {
        	// 옷 종류를 key값으로 하여 해당 key에 매핑되는 value에 대하여
            // 없을 경우 1을 아닐경우 해당 value + 1을 저장
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);
        }
        if (map.keySet().size() > 1) { 
        	// 종류가 복수일 경우 각 의상별 개수 + 1을 곱해준 후
            // 전부 입지 않는 경우 1을 빼준다.
            int multi = 1;
            for (String key : map.keySet()) multi *= map.get(key) + 1;
            answer += multi - 1;
        } else {
        	// 종류가 한가지일 경우 해당 옷의 개수만큼이 정답이다.
            answer = clothes.length;
        }
        return answer;
    }
}

• 옷 종류의 개수에 따라서 나눠서 풀었습니다.
• 옷 종류가 여러개일 경우 각 옷별로 선택의 경우가 옷 개수 + 1(안입는 경우)
• 따라서 종류별 (옷 개수 + 1)을 곱해준 후 모든 옷을 안입는 경우 1을 빼주면 됩니다.
• 예시: (모자 개수 + 1) (코트 개수 + 1) (바지 개수 + 1) - 1(벌거벗은 임금님)
• 우리 코니...! 날이 더워도 옷은 꼭 챙겨입으렴...!

회고

• 코드를 초기화해서 주석이 날라갔지만 오늘은 필요 기능을 정의하고 문제를 풀었습니다.
• 과거에 확률을 공부했으니 문제를 풀었습니다. 역시 수리적 사고력을 꾸준히 키워야겠습니다.