프로그래머스_해시_위장 (JAVA)

문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.    스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.   제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의 모든 원소는 문자열로 이루어져 있습니다. 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다. 스파이는 하루에 최소 한 개의 의상은 입습니다.   입출력 예입출력 예 설명 예제 #1 headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.     예제 #2 face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

 

 

요약하면 여러 집합들이 있는데 해당 집합들의 원소를 한 개 이하로 빼서 조합할 수 있는 경우의 수를 구하는 문제입니다.

 

 

---

 

 

먼저 주어진 배열의 두 번째 값이 집합의 이름입니다. 집합은 여러 개 중복으로 있을 수 있고, 각자가 가지고 있는 값(의상)은 모두 다릅니다. 따라서 각 집합이 몇 개의 원소를 가지고 있는지만 파악하면 되는 간단한 문제입니다.

 

각 집합이 가지고 있는 원소를 해시를 사용해 쉽게 구하는 것은 '완주하지 못한 선수' 문제와 동일합니다. 값을 HashMap에 넣으면서 Value값을 1씩 업데이트해주면 됩니다. 

 

[알고리즘 문제 풀이] - 프로그래머스-해시-완주하지 못한 선수 (JAVA)

 

 

그리고 각 집합이 가지고 있는 원소의 갯수가 정해지면 1씩 더해준 뒤 모두 곱해주고 마지막에 1을 빼주면 됩니다. 통계적인 원리인데, 만약 3개짜리 집합과 2개짜리 집합이 있다면 3개짜리에서는 각자의 원소와 아예 안뽑을 경우까지 4가지 경우의 수가 있고 2개짜리에서는 마찬가지로 3가지 경우의 수가 생깁니다. 둘 다 아예 안뽑을 경우를 가지기 때문에 둘 다 안뽑힐 경우의 수 1은 마지막에 제외를 해주는 것이죠.

 

원리도 쉽고 해시를 이용하는 방식도 기존 문제와 동일하니 코드만 첨부합니다.

 

import java.util.HashMap;
import java.util.Map.Entry;

public class Solution {

	public int solution(String[][] clothes) {

		HashMap<String, Integer> map = new HashMap<String, Integer>();

		for (int i = 0; i < clothes.length; i++) {

			// 종류
			String key = clothes[i][1];

			// 종류별 요소 갯수
			map.put(key, map.getOrDefault(key, 0) + 1);
		}

		int answer = 1;

		for (Entry<String, Integer> entry : map.entrySet()) {

			answer *= entry.getValue() + 1;

		}
		return answer - 1;
	}
}