[코딩테스트 고득점 Kit] 해시 4 - 위장

코딩테스트 연습 - 위장

프로그래머스

 

이 문제의 핵심은 HashMap인 것 같은데… 조합 아이디어 생각하는게 조금 더 어려웠다.

조합이라기보다는 부분집합 이라는 개념으로 생각해야 쉬운데 의상을 안 입는 선택지를 추가하면

경우의 수처럼 종류별 옷을 다 곱해서 쉽게 구할 수 있다.

그리고 마지막으로 공집합 하나를 빼주면 끝

 

Java - HashMap 사용

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        // map (의상종류 - 개수)
        HashMap<String, Integer> cMap = new HashMap<String, Integer>();
        
        for(int i=0; i < clothes.length; i++){
            if(cMap.containsKey(clothes[i][1])){
                cMap.put(clothes[i][1], cMap.get(clothes[i][1]) + 1);
            }else{
                //의상 안 입는 선택지 추가
                cMap.put(clothes[i][1], 2);
            }
        }
        // 옷 종류별 개수 곱한 뒤 공집합 제거
        Integer answer = 1;
        for (Integer val : cMap.values()) {
            answer *= val;
        }
        return answer - 1;
    }
}

 

Python - Dictionary 사용 (HashMap)

import math
from itertools import combinations

def solution(clothes):
    cMap = {}
    # map (의상종류 - 개수)
    for cloth in clothes:
        if cMap.get(cloth[1]) :
            cMap[cloth[1]] += 1
        else:
            # 의상 안 입는 선택지 추가
            cMap[cloth[1]] = 2
    
    # 모두 곱한 뒤 공집합 뺌
    return math.prod(cMap.values()) - 1