Programmers 42578. 위장

Title

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
해시	lv.2	2시간	✅

설계 방법

실패

Map 자료구조에 종류 : 옷 개수를 담는다.
가능한 모든 의상 조합을 찾는다. getAllCombinations([...hashMap.values()])
의상의 종류가 하나라면 옷 개수를 더하고, 의상의 종류가 여러 개라면 종류별 옷개수를 모두 곱해서 최종 결과에 더한다.

성공

가능한 모든 조합을 직접 구해서 계산하지 않음.
의상의 종류를 입지 않는 경우를 추가해 계산.
예를 들어 얼굴 : 3, 상의 : 2, 하의 : 1 이라면 총 가능한 개수는 (3+1) * (2+1) * (1+1) -1 = 13
+1은 착용하지 않은 경우가 추가 되기 때문이고 마지막 -1은 옷을 입지 않은 경우는없기 때문

코드

실패

javascript

function solution(clothes) {
	const hashMap = clothes.reduce(
		(acc, cur) => acc.set(cur[1], (acc.get(cur[1]) || 0) + 1),
		new Map(),
	);

	let answer = getAllCombinations([...hashMap.values()]).reduce(
		(acc, cur) =>
			acc +
			cur.reduce((acc, cur, idx) => (idx === 0 ? acc + cur : acc * cur), 0),
		0,
	);

	return answer;
}

const getKCombinations = (set, k) => {
	const results = [];
	if (k === 1) {
		return set.map((i) => [i]);
	}

	set.forEach((fixed, i, set) => {
		const combinations = getKCombinations(set.slice(i + 1), k - 1);
		results.push(...combinations.map((combination) => [fixed, ...combination]));
	});

	return results;
};

const getAllCombinations = (set) => {
	const results = [];
	for (let k = 1; k <= set.length; k++) {
		const kCombinations = getKCombinations(set, k);
		results.push(...kCombinations);
	}
	return results;
};

function solution(clothes) {
	const hashMap = clothes.reduce(
		(acc, cur) => acc.set(cur[1], (acc.get(cur[1]) || 0) + 1),
		new Map(),
	);

	let answer = getAllCombinations([...hashMap.values()]).reduce(
		(acc, cur) =>
			acc +
			cur.reduce((acc, cur, idx) => (idx === 0 ? acc + cur : acc * cur), 0),
		0,
	);

	return answer;
}

const getKCombinations = (set, k) => {
	const results = [];
	if (k === 1) {
		return set.map((i) => [i]);
	}

	set.forEach((fixed, i, set) => {
		const combinations = getKCombinations(set.slice(i + 1), k - 1);
		results.push(...combinations.map((combination) => [fixed, ...combination]));
	});

	return results;
};

const getAllCombinations = (set) => {
	const results = [];
	for (let k = 1; k <= set.length; k++) {
		const kCombinations = getKCombinations(set, k);
		results.push(...kCombinations);
	}
	return results;
};

성공

javascript

const solution = (clothes) =>
	Object.values(
		clothes.reduce((acc, cur) => {
			acc[cur[1]] = (acc[cur[1]] || 1) + 1;
			return acc;
		}, {}),
	).reduce((acc, cur) => (acc === 0 ? acc + cur : acc * cur), 0) - 1;

module.exports = solution;

const solution = (clothes) =>
	Object.values(
		clothes.reduce((acc, cur) => {
			acc[cur[1]] = (acc[cur[1]] || 1) + 1;
			return acc;
		}, {}),
	).reduce((acc, cur) => (acc === 0 ? acc + cur : acc * cur), 0) - 1;

module.exports = solution;

시간 복잡도

실패

hashMap 구성 : O(N), getAllCombinations : O(nC1 + nC2 + nC3 + ... nCn) = O(2^n)

성공

hashMap 구성 : O(N), 맵 순회 : O(M), (M < 4)

O(N)+ O(M)

어려웠던 점

테스트 케이스 1에 대해 런타임 에러가 발생하는데 아마 재귀 호출로 인한 stack overflow 문제인 듯하다.
모든 조합을 구하는 방식으로 구현했는데, 조합 알고리즘이 꽤 어려웠다.
굳이 조합을 구하지 않아도 되는 수식을 찾는 것을 생각지 못했다.

Programmers 42578. 위장

설계 방법 #

실패 #

성공 #

코드 #

실패 #

성공 #

시간 복잡도 #

실패 #

성공 #

어려웠던 점 #

참고자료 #

설계 방법

실패

성공

코드

실패

성공

시간 복잡도

실패

성공

어려웠던 점

참고자료