문제 출처
문제
'스카피'는 새로운 코스요리 메뉴를 구성하기로 했다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열(오름차순)에 담아 return 하도록 solution 함수를 완성해 주세요.
나의 풀이
1차 시도(60/100)
단순히 각 길이별 최대값을 반환하면 되는 것이므로 구현 자체는 어렵지 않았다. 다만 메뉴 뽑는 과정에서 재귀함수를 써서 시간초과가 발생했다. 재귀함수 최적화를 해야 할 것 같은데 그게 감이 안 잡힌다.
function comb(arr, select, tray) {
let ch = Array.from({length:arr.length}, () => 0);
let answer = [];
function dfs() {
if(tray.length>select) return;
if(tray.length===select) answer.push(tray.slice());
else{
for(let i=0; i<arr.length; i++) {
if(ch[i]===0) {
ch[i]=1;
if(!tray.includes(arr[i])) tray.push(arr[i]);
dfs();
ch[i]=0;
tray.pop();
}
}
}
}
dfs();
for(let i=0; i<answer.length; i++) {
answer[i] = answer[i].sort().join('');
}
return [...new Set(answer)];
}
function solution(orders, course) {
let menu = {};
for(let i=0; i<orders.length; i++) {
orders[i] = orders[i].split('');
for(let j=0; j<course.length; j++) {
let tmp = comb(orders[i], course[j], []);
tmp.forEach(el => menu[el] = (menu[el] || 0) + 1);
}
}
let menuMax = Array.from({length:course[course.length-1]+1}, () => 0);
let menuList = {};
for(let x in menu) {
// console.log(x, x.length, menu[x]);
if(menu[x]>1) menuList[x] = menu[x];
if(menuMax[x.length] < menu[x]) menuMax[x.length] = menu[x];
}
let result = [];
for(let x in menuList) {
if(menuList[x] === menuMax[x.length]) result.push(x);
}
return result.sort();
}
console.log(
// solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4])
// solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2, 3, 5])
solution(["XYZ", "XWY", "WXA"], [2, 3, 4])
);2차 시도 (통과)
메뉴를 뽑는 과정에서 재귀를 최적화했더니 통과되었다.
조합 알고리즘은 여기를 참고했다.
// function comb(arr, select, tray) {
// let ch = Array.from({length:arr.length}, () => 0);
// let answer = [];
// function dfs() {
// if(tray.length>select) return;
// if(tray.length===select) answer.push(tray.slice());
// else{
// for(let i=0; i<arr.length; i++) {
// if(ch[i]===0) {
// ch[i]=1;
// if(!tray.includes(arr[i])) tray.push(arr[i]);
// dfs();
// ch[i]=0;
// tray.pop();
// }
// }
// }
// }
// dfs();
// for(let i=0; i<answer.length; i++) {
// answer[i] = answer[i].sort().join('');
// }
// return [...new Set(answer)];
// }
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]);
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = getCombinations(rest, selectNumber - 1);
const attached = combinations.map((combination) => [fixed, ...combination]);
results.push(...attached);
});
for(let i=0; i<results.length; i++) results[i] = results[i].sort().join('');
return results;
}
function solution(orders, course) {
let menu = {};
for(let i=0; i<orders.length; i++) {
orders[i] = orders[i].split('');
for(let j=0; j<course.length; j++) {
let tmp = getCombinations(orders[i], course[j]);
tmp.forEach(el => menu[el] = (menu[el] || 0) + 1);
}
}
let menuMax = Array.from({length:course[course.length-1]+1}, () => 0);
let menuList = {};
for(let x in menu) {
// console.log(x, x.length, menu[x]);
if(menu[x]>1) menuList[x] = menu[x];
if(menuMax[x.length] < menu[x]) menuMax[x.length] = menu[x];
}
let result = [];
for(let x in menuList) {
if(menuList[x] === menuMax[x.length]) result.push(x);
}
return result.sort();
}
console.log(
solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4])
// solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2, 3, 5])
// solution(["XYZ", "XWY", "WXA"], [2, 3, 4])
);위 조합 알고리즘을 간단히 요약하자면,
4C3이면 [1,2,3]과 [3,2,1]처럼 순서가 바뀌어도 하나의 조합으로 취급해야 한다. [1,2,3,4] 중에서 [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]처럼 도출하면 된다.
그렇다면, [_, _, _, _]일 때 첫번째 자리에는 하나를 고정하고 나머지 3개 원소 중에서 2개를 선택하면 된다.
두번째 자리에는 첫번째 자리에 쓴 원소를 제외하고 나머지 2개 원소 중에서 1개를 선택하면 된다. 이 과정을 반복하면 된다. (유사한 원리로 푼 풀이 참고).
이걸 재귀로 구현한다면,
- 종료 조건은 1개 원소를 선택할 때가 된다. 1개 원소를 선택한다는 건 마지막번째 자리까지 왔다는 의미이므로.
- forEach 문으로, 배열의 모든 원소들이 처음부터 끝까지 한번씩 고정(fix)되도록 한다
- 고정된 값(fixed)들에 대해 나머지 자리수에 대한 조합을 구한다. 이때 선택하는 개수는 줄어들어야 한다.
단순 조합이므로 중복해서 쓸 필요가 없다. 예를 들어 1이 fixed일 때 [1,2,3]를 구했다면, 2가 fixed일 때 1을 다시 쓸 필요가 없다. forEach를 사용하면 이를 구할 수 있다. index는 계속해서 전진하고 앞에서 한번이라도 쓴 index는 이후에 사용하지 않게 된다.
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1); // 해당하는 fixed를 제외한 나머지 뒤
const combinations = getCombinations(rest, selectNumber - 1); // 나머지에 대해서 조합을 구한다.
const attached = combinations.map((combination) => [fixed, ...combination]); // 돌아온 조합에 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
}
const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]또 다른 재귀 조합
function combination(elements, k) {
let prev_elements = [];
let results = [];
function dfs(elements, k) {
if (prev_elements.length === k) {
const tmp = prev_elements.slice().join('');
results.push(tmp);
return ;
}
for (let i = 0; i < elements.length; i++) {
let next_elements = elements.slice(i + 1, elements.length);
prev_elements.push(elements[i]);
dfs(next_elements, k);
prev_elements.pop();
}
}
dfs(elements, k);
return results;
}순열은 조합에서 나아가 순서를 고려해야 한다.
즉, fixed가 1일 때, [1,2,3]을 썼다해도, fixed가 2일 때 1을 다시 사용할 수 있어야 한다. 그러므로 조합 때처럼 단순히 rest를 뒤에 위치한 나머지로 잡는 게 아니라, 순열 때는 rest를 제외한 앞뒤 모두로 잡아야 한다.
혹은 조합을 구한 뒤 공식을 통해 구할 수도 있다.
nPr = nCr * r!
const getPermutations= function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열
console.log(origin[index], rest);
const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};
const example = [1,2,3,4];
const result = getPermutations(example, 3);
console.log(result);
// => [
// [ 1, 2, 3 ], [ 1, 2, 4 ],
// [ 1, 3, 2 ], [ 1, 3, 4 ],
// [ 1, 4, 2 ], [ 1, 4, 3 ],
// [ 2, 1, 3 ], [ 2, 1, 4 ],
// [ 2, 3, 1 ], [ 2, 3, 4 ],
// [ 2, 4, 1 ], [ 2, 4, 3 ],
// [ 3, 1, 2 ], [ 3, 1, 4 ],
// [ 3, 2, 1 ], [ 3, 2, 4 ],
// [ 3, 4, 1 ], [ 3, 4, 2 ],
// [ 4, 1, 2 ], [ 4, 1, 3 ],
// [ 4, 2, 1 ], [ 4, 2, 3 ],
// [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]다른 풀이
function solution(orders, course) {
const ordered = {};
const candidates = {};
const maxNum = Array(10 + 1).fill(0);
const createSet = (arr, start, len, foods) => {
if (len === 0) {
ordered[foods] = (ordered[foods] || 0) + 1;
if (ordered[foods] > 1) candidates[foods] = ordered[foods];
maxNum[foods.length] = Math.max(maxNum[foods.length], ordered[foods]);
return;
}
for (let i = start; i < arr.length; i++) {
createSet(arr, i + 1, len - 1, foods + arr[i]);
}
};
orders.forEach((od) => {
// arr.sort는 기본적으로 사전식 배열
const sorted = od.split('').sort();
// 주문한 음식을 사전순으로 배열해서 문자열을 만든다.
// course에 있는 길이만 만들면 된다.
course.forEach((len) => {
createSet(sorted, 0, len, '');
});
});
const launched = Object.keys(candidates).filter(
(food) => maxNum[food.length] === candidates[food]
);
return launched.sort();
}순열, 조합, 중복순열, 중복조합 정리
js에서 순열, 조합을 구하는 프로세스는 다음과 같이 요약할 수 있다.
for문을 사용해 특정 index 자리에서 선택할 수 있는 요소를 선택하고
index + 1번째에 선택할 수 있는 요소들의 범위를 간추려서 재귀함수의 매개변수로 전달해준다.
그리고 선택한 요소의 개수가 필요한 개수와 동일할 경우를 종료 조건으로 만들어 둔다.
순열과 조합의 차이를 만드는 건 요소의 범위를 간추리는 부분인데,
순열은 현재 방문한 index의 요소를 제외한 나머지 요소들을 전부 선택할 수 있다. 반면, 조합은 현재 방문한 index의 요소 이후의 요소들만 선택할 수 있다. 즉, 이미 지나간 요소는 다음 선택 범위에 넣지 않는다.
// 순열 기본 구조
const list = ["a", "b", "c", "d", "e"];
const pick = 3;
const result = [];
const Permutation = (items, listCopy) => {
if (items.length === pick) {
result.push(items);
return;
}
for (let i = 0; i < listCopy.length; i++) {
Permutation(
`${items}${listCopy[i]}`,
listCopy.filter((v, j) => j !== i)
);
}
};
Permutation("", list);
console.log(result);dfs를 처음 배울 때 내가 많이 사용했던 구조인데,
변수를 사용하지 않고 매개변수 내에서 문제를 해결하는 방법이다.
자리를 바꿔주고 재귀가 종료되면 다시 자리를 원상복구하는 방식인데,
사실 js 코딩테스트에서는 이 정도의 최적화로는 통과하기 힘들 수 있다. 어쨌든 재귀이기 때문이다.
// 순열 최적화
const list = ["a", "b", "c", "d", "e"];
const pick = 3;
const result = [];
function Swap(i, j) {
[list[i], list[j]] = [list[j], list[i]];
}
function Permutation(i) {
if (i === pick) {
result.push(list.slice(0, i).join(""));
return;
}
for (let j = i; j < list.length; j++) {
Swap(i, j);
Permutation(i + 1);
Swap(j, i);
}
}
Permutation(0);
console.log(result);// 조합 기본 구조
const list = ["a", "b", "c", "d", "e"];
const pick = 3;
const result = [];
function Combination(items, index) {
if (items.length === pick) {
result.push(items);
return;
}
for (let i = index; i < list.length; i++) {
Combination(`${items}${list[i]}`, i + 1);
}
}
Combination("", 0);
console.log(result);지금까지는 현재 선택한 요소를 다음 선택 범위에서 제외했지만,
중복의 경우 현재 선택한 요소도 선택할 수 있게 만들면 된다.
그 외의 순열과 조합의 차이는 여전하다. 중복순열은 모든 요소를 선택할 수 있는 것이고, 중복조합은 이전에 선택한 요소들을 포함하지 않는다.
중복 순열은 매번 모든 요소를 선택할 수 있기에 매번 for i=0으로 고정해준다.
// 중복 순열
const list = ['a', 'b', 'c', 'd', 'e'];
const pick = 3;
const result = [];
function pwr(items) {
if(items.length === pick) {
result.push(items);
return;
}
for (let i = 0; i < list.length; i ++) {
pwr(`${items}${list[i]}`);
}
}
pwr('');중복 조합은 이전에 선택한 요소들을 선택할 수 없기에 for i= idx;로 잡아야 한다.
// 조합
const list = ['a', 'b', 'c', 'd', 'e'];
const pick = 3;
const result = [];
function pwc(items, index) {
if(items.length === pick) {
result.push(items);
return;
}
for (let i = index; i < list.length; i ++) {
pwc(`${items}${list[i]}`, i);
}
}
pwc('', 0);참고
JavaScript로 순열과 조합 알고리즘 구현하기
[javascript] 순열, 조합, 중복순열, 중복조합
