Programmers[42578] - 위장[Level2]

링크

프로그래머스

문제설명

• 조합 경우의 수

문제풀이

• 조합 경우의 수 = 종류별 가능한경우 다 곱한 후, 아무것도 안고른 경우 빼기

문제코드

import java.util.HashMap;

public class Solution42578_위장 {

    public static int solution(String[][] clothes) {
//        {종류 , 종류개수}
        HashMap<String, Integer> hm = new HashMap<String, Integer>();

        for (String[] cloth : clothes) {
            if(hm.containsKey(cloth[1])){
                hm.put(cloth[1], hm.get(cloth[1])+1);
            }
            else {
                hm.put(cloth[1],1);
            }
        }

        int answer = 1;
        for (int val : hm.values()) {
            answer*=(val+1);
        }
        return answer-1;
    }

    public static void main(String[] args) {
        System.out.println(solution(new String[][] {
            {"yellow_hat", "headgear"},
            {"blue_sunglasses", "eyewear"},
            {"green_turban", "headgear"}
        }));
        System.out.println(solution(new String[][] {
            {"crow_mask", "face"},
            {"blue_sunglasses", "face"},
            {"smoky_makeup", "face"}
        }));
    }
}

아쉬운점

• 사실 해쉬문제라 하기에는 종류의 개수가 5개뿐이라.. 굳이 해쉬 써야하나 싶기도 함.

  • 해쉬 구현에 의의를 두자.

• Iterator 쓰는 법을 모름

• Iterator<Integer> it = map.values().iterator();
         while(it.hasNext()) {
             answer *= it.next().intValue()+1;
         }

  이렇게 사용한다.

다른사람 풀이

• dp로 풀 수 있음
• 종류N선택안했을 경우 = NX, 종류N선택 = NO 로 표시한다
• ~N은 N종류까지 선택했을 경우를 의미

1X	1O
~2X = 1X * 2X + 1O * 2X	~2O = 1X * 2O + 1O * 2O
~3X = ~2X * 3X + ~2O * 3X	~3O = ~2X * 3O + ~2O * 3O
...	...
~NX = ~(N-1)X * NX + ~(N-1)O * NX	~NO = ~(N-1)X * NO + ~(N-1)O * NO

• ~N = ~NX + ~NO인데 여기서 1X2X...NX인 경우 1 빼주면 된다.
• dp로는 생각도 못했는데 dp적 사고를 개발하기 좋은 접근법인 것 같다.