[프로그래머스] 위장

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

코딩테스트 연습 - 위장

풀이과정

재귀를 이용하여 모든 경우의 수를 구했으나 시간초과가 발생하였다.

 

그래서 직접 모든 경우의 수식을 세워 문제를 해결했다.

(종류 + 1) * (종류 + 1) .... 을 하게 되면 정답이 나온다. +1을 하는 이유는 그 종류의 장비를 입지 않은 경우이다.

마지막에 -1을 하게 되는데, 최소 한가지의 장비는 착용하기 때문에 모두 벗는 경우는 제외한다.

 

 

 

소스코드

function solution(clothes) {
	var answer = 0;
	var clothesType = [];
	var keys = [];

	for (var i = 0; i < clothes.length; i++) {
		var idx = keys.indexOf(clothes[i][1]);
		if (idx != -1){
			clothesType[idx].push(clothes[i][0]);
		}
		else {
			var type = [clothes[i][0]];
			clothesType.push(type);
			keys.push(clothes[i][1]);
		}
 	}
	//재귀 시간초과
	// function solve(cur, depth, count, sum) {
	// 	if (depth == count) {
	// 		answer += sum;
	// 		return;
	// 	}
	// 	for (var i = cur; i < clothesType.length; i++) {
	// 		if (sum == 0) {
	// 			solve(i + 1, depth + 1, count, clothesType[i].length);	
	// 		}
	// 		else {
	// 			solve(i + 1, depth + 1, count, sum * clothesType[i].length);
	// 		}
	// 	}
	// }
	for (var i = 0; i < clothesSize; i++) {
        answer = answer ? answer * (clothesType[i].length + 1) : (clothesType[i].length + 1);
	}
	return answer;
}