Programmers 의상

 

 

- 목차

 

소개.

"프로그래머스 의상" 관련 문제의 웹링크입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42578#

프로그래머스

 

 

문제 분석.

 

위 문제는 조합의 수학적인 의미를 이해하고 구현 가능 여부를 파악하는 문제입니다.

각 종류별로 의상들이 존재하고, 종류별 의상을 최대한 1개씩 착용해야합니다.

 

예를 들어,

headgear 5개 와 eyewear 5개의 의상이 존재한다고 가정하겠습니다.

headgear : a,b,c,d,e

eyewear : f,g,h,i, j

가 존재합니다.

이때 가능한 조합은 아래와 같습니다.

 

하나씩 착용하는 경우 : a, b, c, d, e, f, g, h, i, j

두개씩 착용하는 경우 : (a,f), (a,g), (a,h), (a,i), (a,j) ... (e,j)

즉, 35 가지의 경우가 존재하는데요.

이를 조합의 관점에서 나타내면

 

1개씩 착용하는 경우는 10C1 -> 10

2개씩 착용하는 경우는 5C1 * 5C1 -> 25

즉 10 과 25 를 더하여 35를 얻을 수 있습니다.

 

또 다른 예시로

headgear 3개 와 eyewear 3개, foot 3개의 의상이 존재한다고 가정하겠습니다.

headgear : 1,2,3

eyewear : 4,5,6

foot : 7,8,9

 

하나씩 착용하는 경우 : 1,2,3,4,5,6,7,8,9

두개씩 착용하는 경우 : (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), ... (6, 9)

세개씩 착용하는 경우 : (1,4,7),(1,4,8),(1,4,9), ... , (3,6,9)

 

이 경우에는 조합의 경우를 찾는 것이 복잡하게 됩니다.

 

가장 쉬운 방법은

각각의 종류의 가짓수에 1을 더하여 조합을 구하는 방식인데요.

가짓수에 1을 더하는 이유는 아무 의상도 입지 않는 경우입니다.

따라서

headgear : none, a,b,c,d,e

eyewear : none, f,g,h,i, j

none 인 의상을 추가하여, 6C1 * 6C1 - 1 을 수행하면 손쉽게 의상의 조합을 구할 수 있습니다.

 

문제 풀이.

import java.util.*;

class Solution {
  public long solution(String[][] clothes) {
    Long answer = 1L;
    Map<String, Long> map = new HashMap<>();
    for (String[] cloth : clothes) {
      String name = cloth[0];
      String type = cloth[1];
      if (map.containsKey(type)) {
        map.put(type, map.get(type) + 1L);
      } else {
        map.put(type, 1L);
      }
    }

    for (Map.Entry<String, Long> entry : map.entrySet()) {
      Long num = entry.getValue();
        answer *= (num + 1L);
    }

    answer--;

    return answer;
  }
}