프로그래머스 - 의상

프로그래머스 - 의상

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

class Solution {
	public int solution(String[][] clothes) {
		// 1. 종류 : 이름 맵 생성
		// 2. N+1 * N+1 -1로 구해주기(잆거나 안입거나)
		Map<String, ArrayList<String>> map = new HashMap<>();
		// 1. 맵 생성
		for(String[] clothArr : clothes) {
				map.putIfAbsent(clothArr[1], new ArrayList<>());
				map.get(clothArr[1]).add(clothArr[0]);
		}

		// 2. 계산
		if(map.keySet().size() ==1) {
			Set<String> keys = map.keySet();
			// 어차피 키가 1개라서 바로 리스트 개수 반환
			for(String key : keys) {
				ArrayList<String> list = map.get(key);
				return list.size();
			}
		}

		int result = 1;
		for(Map.Entry<String, ArrayList<String>> a : map.entrySet()) {
			// 전체를 1개씩 입거나(n), 아에 안입는 경우 1
			result *= (a.getValue().size() + 1) ;
		}

		// 전체를 아에 안입는 경우 제외
		return --result;
	}
}

• 구현 방법

  • 만일 의상 종류가 1개라면, N개의 경우의수 리턴 -> 하루 최소 1개의 의상 입어야 하기에 안입는 경우는 없음

    • 모자 A, B, C -> A 또는 B 또는 C 쓰기 가능

  • 만일 의상 종류가 2개 이상이라면 각각의 경우에 대해 하나씩 입거나 안입는 경우 발생

    • 모자 - A, B, C : 3 -> 모자 : A, B, 안입음 / 상의 : C, 안입음

      모자 : A, B
      상의 : C
      -> 모자 A / 상의 x
      -> 모자 B / 상의 x
      -> 모자 A / 상의 C
      -> 모자 B / 상의 C
      -> 모자 x / 상의 C
      -> 모자 x / 상의 x (하루 최소 1개의 의상 입어야 해서 해당 경우 제외)

  • 즉 한 의상의 종류가 2개 이상이라면 각 의상 종류의 경우의 수는 (N + 1(안입음)) 이니,
    이게 종류가 M개라고 하면 (N + 1) ((N+a) + 1) .... (M번 곱) - 1(전체 안입는 경우)가 된다.

• 출처 : 프로그래머스 - 의상