문제 정의
두 개의 문자열 str1과 str2를 인자로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 문자열 str1을 최소 몇 번 반복해야 str2가 그 결과 문자열의 부분 문자열(substring)이 되는지 그 최소 횟수를 반환해야 합니다. 만약 아무리 반복해도 str2가 부분 문자열이 될 수 없다면 -1을 반환하면 됩니다.
예를 들어, 함수에 다음과 같은 입력이 주어진다고 가정해 보겠습니다.
입력
const str1 = 'wxyz';
const str2 = 'yzwxyzwx';
출력
const output = 3;
출력 설명
3을 반환하는 이유는 str1을 세 번 반복한 문자열 안에 str2가 부분 문자열로 포함되기 때문입니다.
해결 방법
가장 직관적인 접근 방식은 str1을 한 번씩 반복해서 이어 붙인 뒤, 매번 str2가 포함되어 있는지 확인하는 것입니다. 다만 무한히 반복하지 않도록 종료 조건이 필요합니다.
핵심 아이디어는 다음과 같습니다.
- str1을 반복해서 붙일 때마다 현재 문자열에 str2가 포함되는지 검사합니다.
- 현재 문자열의 길이가 str2 길이의 2배를 넘었는데도 찾지 못했다면, 더 이상 반복해도 의미가 없으므로 -1을 반환합니다.
str2가 부분 문자열이 되려면 반복된 문자열의 길이가 최소한 str2의 길이만큼은 되어야 하고, 경계에 걸치는 경우를 고려해도 str2 길이의 2배를 넘는 시점까지 찾지 못했다면 존재할 가능성이 없기 때문입니다.
예제 코드
다음은 위 로직을 구현한 코드입니다.
const str1 = 'wxyz';
const str2 = 'yzwxyzwx';
const countRepeat = (str1 = '', str2) => {
let i = 1;
let current = str1;
while (true) {
// 현재 문자열에 str2가 포함되어 있는지 확인
if (current.indexOf(str2) >= 0) {
return i;
}
// 더 이상 반복해도 찾을 수 없는 경우
if ((current.length > str2.length * 2) && i > 2) {
return -1;
}
current += str1;
i += 1;
}
};
console.log(countRepeat(str1, str2));
실행 결과
3
코드 동작 원리
위 코드는 변수 i로 반복 횟수를 추적하고, 변수 current에 str1을 계속 이어 붙여 나갑니다. 매 반복마다 indexOf() 메서드로 str2의 포함 여부를 검사하고, 발견되는 즉시 그 시점의 반복 횟수를 반환합니다.
반면 current의 길이가 str2 길이의 2배를 초과했음에도 두 번 이상 반복했는데도 찾지 못한다면, 이후에는 절대 나오지 않는다고 판단하여 -1을 반환함으로써 무한 루프를 방지합니다. 이러한 조건 덕분에 함수는 항상 유한한 시간 안에 결과를 보장할 수 있습니다.