[프로그래머스] 위장

jungwoo jo·2021년 8월 25일
0

문제 설명

옷의 종류와 종류에 따라 옷들이 주어진다. 이때 주어진 옷 종류 별로 옷을 고를 때의 경우의 수를 모두 구하는 문제이다. 옷의 종류는 얼굴, 상의, 하의, 겉옷으로 무조건 한 개 이상은 입어야 한다. 종류 중에 하나 상의만 입는 것도 경우의 수에 포함된다.

  • 제한 사항
    • 입력 값으로 [의상의 이름, 의상의 종류]가 제공된다.
    • 의상의 수는 1 ~ 30개이다.
    • 중복된 이름의 의상은 주어지지 않는다.
    • 입력은 모두 문자열이다.
    • 문자열 길이는 1 ~ 20 모두 소문자 또는 '_' 으로 이뤄져있다.
    • 최소 한 개의 의상은 무조건 입는다.

문제 링크 : 위장

풀이

처음 의상의 수가 최대 30개라서 bruto force로 풀 수 있을 거라 생각하지만 30개에서 의상의 종류가 다양하게 나눠지고 거기서 또 옷을 입거나 안입는 경우의 수까지 고려해야하기 때문에 경우의 수가 엄청 커지고 구현하기 복잡해진다. 따라서 수학적으로 경우의 수를 계산하는 방법이 필요하다.

만약 상의 : 2, 하의 : 1 일 때

상의와 하의 둘 중에 하나를 안입는 경우의 수를 구해야 하기 때문에 각 의상 종류에 안입는 경우의 수를 생각해서 1 더해준 뒤 모든 종류를 곱해주면 된다.(아무것도 안입는 경우는 빼줘야 한다)

1. 상의1 + (안입는다)
2. 상의2 + (안입는다)
3. 하의1 + (안입는다)
4. 상의1 + 하의1
5. 상의2 + 하의1
6. (안입는다) + (안입는다) <-- 아무것도 안입는 경우는 제외

따라서 (상의 2 + 1) * (하의 1 + 1) - 1(안입는 경우) 라는 식이 나온다.

코드

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i=0;i<clothes.length;i++) {
            int idx = 1;
            if (map.containsKey(clothes[i][1])) {
                idx = map.get(clothes[i][1]) + 1;
            }
            map.put(clothes[i][1], idx);
        }
        answer = 1;
        for (String str : map.keySet()) {
            answer *= map.get(str) + 1;
        }
        return answer - 1;
    }
}
profile
개발이 즐거운 사람

0개의 댓글