문제
하나의 문자열로 합쳐진 순열을 다시 복구하는 문제이다. 일단 순열의 정의부터 아는 것이 좋다. 순열은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관 있게 r개의 원소를 선택하거나 혹은 나열하는 것이다.
kriii는 이러한 순열을 생각해서 중복되는 수가 없도록 수열을 다시 복구하면 된다. 중복되는 수가 없도록 하기 위해서는 루프를 돌면서 이전에도 중복된 수가 있는지 검사를 해야한다.
따라서 해당 문제는
- 각 수를 분할하여 계산
- 메모이제이션이 필요 하기 때문에, dp로 풀어야 할 것 같다고 생각했다.
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs").readFileSync(INPUT_FILE).toString().trim();
const dpArr = new Array();
let pstring = "";
for (let i = 0; i < inputs.length; i++) {
pstring += inputs[i];
if (!dpArr.includes(pstring)) {
dpArr.push(pstring);
pstring = "";
continue;
}
for (let j = i + 1; j < inputs.length; j++) {
pstring += inputs[j];
if (!dpArr.includes(pstring)) {
dpArr.push(pstring);
pstring = "";
i = j;
break;
}
}
}
console.log(dpArr.join(" "));
그렇게 처음 만들어진 코드 제출하자마자 바로 컷당했다..
결국 알고리즘 분류를 보았는데 백트래킹으로 풀어야 한다고 한다.
kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.
조건 중 하나를 제대로 보지 않았다. 순열에 들어가는 수는 제한이 있었다.
이 말의 뜻은 곧 순열은 1부터 50까지의 수 중에 N개의 수를 고르면 해당 N개의 수는 1부터 N까지 숫자가 무조건 한 번씩은 사용이 되어야 하고, 중복이 없어야 한다.
그렇다면 매 수가 가면서 해당 수를 넣었을 때와 넣지 않았을 때로 나누어 계산한 후, 중간에 조건이 맞지 않는다면 빠꾸 시키는 백트래킹 형식으로 가면 되지 않을까?
결국 ai의 도움을 통해 풀었다… 백트래킹이 익숙치 않다보니 로직은 조금 더 보면서 익혀야 할 것 같다.
// 백트래킹 함수
function backtrack(index, path, used) {
// 문자열 끝에 도달했을 때
if (index === inputs.length) {
return path.length > 0 ? path : null;
}
for (let length = 1; length <= 2; length++) {
if (index + length > inputs.length) continue;
// 현재 위치에서 length만큼의 숫자 추출
const num = parseInt(inputs.slice(index, index + length));
// 유효한 숫자인지 확인
if (isValid(num, used)) {
// 현재 숫자를 사용했다고 표시
const newUsed = new Set(used);
newUsed.add(num);
// 다음 단계로 진행
const result = backtrack(index + length, [...path, num], newUsed);
if (result) {
return result;
}
}
}
}순열의 숫자의 경우 1~50까지의 수여야만 하기 때문에 수는 1자리 수가 될 수도 있고, 2자리 수가 될 수도 있다. 하지만 그 이상은 가지 못한다. 따라서 1자리 수와 2자리 수를 구분하여 백트래킹을 진행했다.
function isValid(num, used) {
return num >= 1 && num <= Math.min(inputs.length, 50) && !used.has(num);
}해당 수가 유효한지 검사하는 함수의 경우 맨 처음엔 고정적으로 50까지의 수라 했으니 50을 해야겠다!라고만 생각했다. 하지만 이렇게 될 경우 나중에 더 큰 수가 나오면서 순열의 조건을 해치는 경우가 있을 수 있으므로 받은 문자열의 길이를 통해 최대한 가질 수 있는 순열의 수를 유추했다. 하지만 이렇게 유추했을 때 50을 넘어버리는 경우가 있기 때문에 Math.min을 통해 조건부로 조건을 넘겨줄 수 있도록 하였다.
const result = backtrack(0, [], new Set());
// 결과가 있고, 유효한 순열인지 확인
if (result) {
const maxNum = Math.max(...result);
const expectedSet = new Set(Array.from({ length: maxNum }, (_, i) => i + 1));
const resultSet = new Set(result);
// 1부터 maxNum까지의 모든 숫자가 정확히 한 번씩 사용되었는지 확인
if (
result.length === maxNum &&
JSON.stringify([...expectedSet].sort()) ===
JSON.stringify([...resultSet].sort())
) {
console.log(result.join(" "));
}
}
백트래킹을 진행한 후에는 result에 순열이 담기게 되는데, 조건을 만족하는 것들이 여러개라면 하나만 받으면 되므로 조건이 맞았을 때 바로 return하도록 해서 그 후에 가져온 결과를 검사했다. 유효한 수인지를 검사하고 이에 따라 1~최대 순열의 길이까지의 수들이 모두 사용되었는지를 검사하여 결과를 내보냈다.
백트래킹,,,,어렵군,,,,