Q. 제한사항이 이런데, 50,000,000개가 될 수도 있는 중복 순열을 모두 구하신다고요?
A. 네!!
지금은 공부하는 단계니까, 이런 것도 되려나 싶은 것들도 모두 해보고 싶은 마음입니다. ㅋ
실전이라면, 안될 것 같은 로직은 바로 쳐내고 다른 아이디어를 생각하는 게 현명한 것이겠지만요
첫 번째 시도 (오답, 60.0/100)
code
function solution(n) {
const nums = [1, 2, 4];
const answer = [];
let round = 1;
while (answer.length < n) {
answer.push(...getDupPermutations(nums, round).map(v => v.join('')));
round += 1;
}
return answer[n - 1];
}
function getDupPermutations(arr, n) {
let result = [];
if (n === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
const subPermutations = getDupPermutations(origin, n - 1);
const attached = subPermutations.map(v => [fixed, ...v]);
result.push(...attached);
});
return result;
}
review
그렇게 됐습니다.
중복 순열을 구하는 함수 자체는 제대로 동작하는 것 같고,
콜 스택이 무한하고, 배열에 무한히 많은 원소를 저장할 수 있다는 유니콘 같은 상황이라고 가정한다면,
정확도는 ㄱㅊ은 아이디어였지 않을까 생각합니다.
이건.. ⓐ answer 배열에 너무 많은 원소가 들어가는 문제 보다는,
getDupPermutations 함수와, 또 그 안에서 호출되는 arr.forEach()가 너무너무너무 많이 호출되어,
ⓑ 호출되는 함수의 수가 콜 스택의 한계치를 초과해 버리는 문제가 치명적이었을 것 같습니다.
근데 또 해보고 싶은 게 있어서 해봤습니다 (?)
그건 바로.. answer를 환형 큐로 만들어 보는 것입니다. ㅋ
두 번째 시도 (오답, 60.0/100)
code
const QUEUE_SIZE = 1000;
function solution(n) {
const nums = [1, 2, 4];
const answer = new Array(QUEUE_SIZE);
let round = 1;
let i = 0; // answer[i % QUEUE_SIZE]
while (i < n) {
const permutations = getDupPermutations(nums, round++).map(v => v.join(''));
for (const item of permutations) {
answer[i++ % QUEUE_SIZE] = item;
if (i >= n) break;
}
}
return answer[(i - 1) % QUEUE_SIZE];
}
function getDupPermutations(arr, n) {
let result = [];
if (n === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
const subPermutations = getDupPermutations(origin, n - 1);
const attached = subPermutations.map(v => [fixed, ...v]);
result.push(...attached);
});
return result;
}
review
ㅋ
정답에는 가까워 질 수 없었지만,
환형 큐를 써보자는 목표는 달성할 수 있었습니다.
중복 순열 모두 구하는 방법 탈락!!
깔끔하게 포기!!
세 번째 시도 (정답)
code
function solution(n) {
return convertTo124(n);
}
function convertTo124(n) {
let result = [];
const convertTable = [4, 1, 2];
// 나머지 계산 결과(배열의 index 값에 대응)에 따른 result 출력 값 매칭
// 3을 3으로 나누었을 때 나머지가 0 -> 4로 변환되어야 함
// 1을 3으로 나누었을 때 나머지가 1
// 2를 3로 나누었을 때 나머지가 2
while (n > 0) {
result = [convertTable[n % 3], ...result];
n = n % 3 === 0 ? n - 1 : n;
n = Math.floor(n / 3);
}
return result.join('');
}
