문자열 GCD란 무엇인가?
수학에서 두 수의 최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나눌 수 있는 가장 큰 수를 의미합니다. 흥미롭게도 이 개념은 문자열에도 그대로 적용할 수 있습니다.
두 문자열의 GCD란, 두 문자열 모두에 존재하는 가장 긴 공통 부분 문자열을 뜻합니다. 여기서 핵심은 단순히 겹치는 부분을 찾는 것이 아니라, 두 문자열이 모두 동일한 패턴의 반복으로 구성되어 있어야 한다는 점입니다.
예시
다음과 같은 두 문자열이 있다고 가정해 보겠습니다.
const str1 = 'abcabc'; const str2 = 'abc';
str1은 'abc'가 두 번 반복된 문자열이고, str2는 'abc'가 한 번 등장합니다. 따라서 두 문자열의 GCD는 다음과 같습니다.
const gcd = 'abc';
구현 방법
두 문자열 str1과 str2를 입력받아 GCD를 계산해 반환하는 JavaScript 함수를 작성해 보겠습니다. 핵심 아이디어는 유클리드 호제법(Euclidean algorithm)과 유사하게, 더 긴 문자열에서 짧은 문자열의 길이만큼 잘라내는 작업을 재귀적으로 반복하는 것입니다.
먼저 중요한 전제 조건이 하나 있습니다. str1 + str2와 str2 + str1을 연결한 결과가 서로 같지 않다면, 두 문자열은 공통 패턴으로 구성될 수 없으므로 빈 문자열을 반환해야 합니다. 예를 들어 'abc'와 'def'처럼 완전히 다른 문자가 섞여 있다면 GCD는 존재하지 않습니다.
코드
const str1 = 'abcabc';
const str2 = 'abc';
const findGCD = (str1 = '', str2 = '') => {
// 연결 순서를 바꿔도 결과가 같지 않으면 공통 패턴이 없음
if (str1 + str2 !== str2 + str1){
return "";
} else if (str1 == str2){
// 두 문자열이 같으면 그 자체가 GCD
return str1;
} else if (str1.length > str2.length){
// 더 긴 문자열에서 짧은 문자열 길이만큼 제거 후 재귀 호출
return findGCD(str1.slice(str2.length), str2);
} else {
return findGCD(str2.slice(str1.length), str1);
}
};
console.log(findGCD(str1, str2));동작 원리
- 유효성 검사: str1 + str2 !== str2 + str1이라면 두 문자열이 같은 기본 패턴으로 이루어질 수 없으므로 빈 문자열 ""을 반환합니다.
- 종료 조건: 두 문자열이 완전히 같아지면 해당 문자열이 곧 GCD입니다.
- 재귀 축소: 길이가 더 긴 문자열에서 짧은 문자열의 길이만큼 앞부분을 잘라낸 뒤, 남은 문자열과 짧은 문자열로 다시 findGCD를 호출합니다. 이는 수의 GCD를 구할 때 나머지 연산을 반복하는 유클리드 호제법과 정확히 같은 구조입니다.
대안: Math.gcd 스타일 접근
재귀적으로 문자열을 자르는 대신, 두 문자열 길이의 최대공약수를 먼저 구하고 그 길이만큼의 접두사를 검증하는 방법도 있습니다.
const gcdOfStrings = (str1, str2) => {
if (str1 + str2 !== str2 + str1) return '';
const gcdLen = (a, b) => (b === 0 ? a : gcdLen(b, a % b));
const len = gcdLen(str1.length, str2.length);
return str1.slice(0, len);
};
console.log(gcdOfStrings('abcabc', 'abc')); // abc두 방식 모두 연결 비교(str1 + str2 === str2 + str1)라는 동일한 핵심 아이디어에 기반하며, 이 검사 하나로 두 문자열이 공통 패턴의 반복인지를 빠르게 판별할 수 있습니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
abc
마무리
이 알고리즘은 문자열 연결 비교 한 번과 재귀 호출 몇 번만으로 해결되며, 유클리드 호제법과 같은 원리로 빠르게 수렴하기 때문에 매우 효율적입니다. LeetCode 1071번 'Greatest Common Divisor of Strings' 문제와도 동일한 접근 방식이므로, 문자열 처리 로직 학습과 코딩 테스트 준비에 모두 유용하게 활용할 수 있습니다.