[프로그래머스] 위장

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장 | 프로그래머스

코드

package Programmers.Level2;

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

public class Camouflage {

	public static void main(String[] args) {

		String[][] clothes ={
				{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}
		};

		int answer = solution(clothes);

		System.out.println(answer);

	}//main

	public static int solution(String[][] clothes) {
			
		// 경우의 수를 찾아서, 산식에 대입해준다.
		Map<String,Integer> m = new HashMap<String,Integer>();
		
		for ( String[] clothe : clothes ) {
			m.put( clothe[1], (m.getOrDefault(clothe[1], 0)+1) );
		}
		
		int answer = 1;
		
		for ( int num : m.values() ) {
			answer*=(num+1);
		}
		
		answer--;
		
		return answer ;
	}
}//class

제출 결과

후기

N종류의 의상이 각각 M개씩 있을 때, 위장을 위해 입을 수 있는 모든 조합이 총 몇가지 인지를 구하는 문제이다.

 

그리고 위장을 위해서는 최소1개의 옷을 반드시 입어야 한다.

 

예를들어 상의3벌, 하의2벌, 모자3개가 있다고 하자.

이때, 최소1개의 옷을 입는 모든 경우의 수는 각 종류별 옷의 갯수에 +1을 해줘서 모두 곱한 후 -1을 빼면 된다.

 

위의 예시에서는 ( 3+1 ) * ( 2+1 ) * ( 3+1 ) 을 곱하고 -1 을 해주면 총 47개의 코디를 할 수 있는것이다.

 

여기서 [ 종류 별 총 갯수 + 1 ] 에서 [ +1 ]의 의미는 해당 종류가 선택되지 않는 경우의 수이다.

 

예를들면, 자음2개 모음2개로 만들 수 있는 한글을 조합해보자. ( 단일 모음,자음도 가능한다고 하자. )

 

자음 : [ ㄱ,ㄴ ] , 모음 [ ㅗ , ㅏ ] 이라고 주어졌을 때

 

자음의 갯수 2개, 모음의 갯수 2개를 세고 

 

[ 자음 + 모음 ]조합으로 가능한 [ 고,가,노,나 ]를 세서 총 8개를 계산하게 된다.

 

여기서 +1의 의미대로 선택되지 않는 수를 조건에 추가해서 계산해보자.

( 여기서는 자음,모음의 갯수를 따로 세지 않겠다. )

 

자음 : [ ㄱ, ㄴ, 자음X ] , 모음 : [ ㅗ, ㅏ , 모음X ]

 

[ ㄱ+모음X ] , [ ㄴ + 모음X ] , [ 자음X, 모음X ] , [ ㅗ + 자음X ] , [ ㅏ + 자음X ]

[ 고 , 가 , 노 , 나 ] 이렇게 선택 될 수 있다.

 

단일자음, 모음의 숫자를 별도로 세주지않아도 선택되지 않는 수를 추가해 줌으로써,갯수를 셀 수 있다.

 

그러나 자음X, 모음X 같이 아무것도 선택되지 않는 경우는 존재 할 수 없다. 그래서 마지막에 -1을 해주는 것이다.

 

총4가지 종류의 갯수가 [ 3,2,3,5 ] 가지의 갯수가 있다고 했을때도 동일하다.

 

정리하면, 해당 종류가 포함되지 않는 경우를 +1 해줌으로서 나머지 경우의 수를 간편하게 구할수 있고.. 모두 선택되지 않는 경우의수 1만큼을 빼주면 된다.

 

여기서 이렇게 경우의수를 구하는 산식하나를 배울 수 있었다.. 적용 할 수 있는 날이 왔으면 좋겠다.

 

Q. N개의 선택 사항이 있을 때, 최소1개이상을 선택하는 조합의 경우의 수를 구할 수 있겠는가 ??