문자열을 인수로 받아, 해당 문자열이 동일한 문자 시퀀스가 반복되어 이루어져 있는지를 판별하는 JavaScript 함수를 작성해 보겠습니다. 함수는 조건을 만족하면 true, 그렇지 않으면 false를 반환합니다.
여기서 주어진 문자열의 길이는 항상 1보다 크며, 반복되는 문자 시퀀스는 최소 한 번 이상 나타나야 한다는 조건이 있습니다.
문제 이해하기
예시를 통해 요구 사항을 살펴보겠습니다.
- "aa" →
true: "a"라는 동일한 문자열 두 개로만 구성되어 있습니다. - "aaa" →
true: "a"라는 동일한 문자열 세 개로만 구성되어 있습니다. - "abcabcabc" →
true: "abc"라는 동일한 문자열 세 개로만 구성되어 있습니다. - "aba" →
false: 동일한 하위 문자열이 최소 두 번 이상 반복되어야 하는데, 그렇지 못합니다. - "ababa" →
false: "ab"가 두 번 반복되긴 하지만 끝에 남는 "a"가 있어 전체가 하나의 패턴으로 구성되지 않습니다.
구현 코드
핵심 아이디어는 다음과 같습니다. 반복 단위가 될 수 있는 하위 문자열의 길이는 전체 문자열 길이의 절반을 넘을 수 없으므로, 1부터 문자열 길이의 절반까지 후보 길이를 순회하면서 검사합니다. 또한 전체 길이가 해당 후보 길이로 나누어떨어지는 경우에만 검사를 진행하면 불필요한 연산을 줄일 수 있습니다.
const checkCombination = (str = '') => {
if( str.length==1 ) {
return true;
};
for(let i = 1; i <= str.length / 2; i++){
if(str.length % i !== 0){
continue;
}
const sub = str.substring(0, i);
if(isRepeating(sub, str)){
return true;
};
};
return false;
}
const isRepeating = (sub, str) => {
if(str.length > sub.length){
let left = str.substring(0,sub.length);
let right = str.substring(sub.length, str.length);
return left===sub && isRepeating(sub,right);
};
return str === sub;
}
console.log(checkCombination('aa'));
console.log(checkCombination('aaa'));
console.log(checkCombination('abcabcabc'));
console.log(checkCombination('aba'));
console.log(checkCombination('ababa'));코드 동작 방식
checkCombination 함수는 1부터 문자열 길이의 절반까지 후보 길이 i를 순회합니다. 전체 길이가 i로 나누어떨어지지 않으면 continue로 건너뛰고, 나누어떨어진다면 앞부분 i개의 문자를 잘라 하위 문자열 sub를 만든 뒤 isRepeating으로 반복 여부를 검사합니다.
isRepeating 함수는 재귀적으로 동작합니다. 검사 대상 문자열이 하위 문자열보다 길면 앞부분이 sub와 일치하는지 확인하고, 나머지 부분에 대해 다시 자기 자신을 호출합니다. 길이가 같아지면 두 문자열이 완전히 일치하는지 비교하여 최종 결과를 결정합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
true true true false false
예상대로 "aa", "aaa", "abcabcabc"는 동일한 패턴의 반복으로 구성되어 true를 반환하고, "aba"와 "ababa"는 완전한 반복 구조가 아니므로 false를 반환하는 것을 확인할 수 있습니다.