두 문자열 A와 B가 있을 때, B를 한 번 이상 이어 붙여 A를 만들 수 있다면 'A는 B로 나누어떨어진다'고 표현합니다. 예를 들어 A = "abcabc", B = "abc"인 경우, A는 B로 나누어떨어집니다.
이번 글에서 다룰 문제는 바로 문자열의 최대공약수(GCD)입니다. 즉, 주어진 두 문자열을 모두 나누어떨어지게 만드는 가장 긴 문자열을 찾아 반환해야 합니다. 예를 들어 두 문자열이 "ABABAB"와 "ABAB"라면, 최대공약수는 "AB"가 됩니다.
풀이 접근 방법
이 문제는 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.
- temp := A와 B 중 더 짧은 문자열을 선택
- m := temp의 길이, x := 1로 초기화
- 결과를 저장할 배열 res를 생성하고 빈 문자열("")을 삽입
- x를 1씩 늘려가며, m이 x로 나누어떨어지고 temp의 앞 x글자를 반복했을 때 str1과 str2가 모두 재현되는지 확인. 조건을 만족하면 해당 부분 문자열을 res에 추가
- 반복이 끝나면 res의 마지막 요소, 즉 가장 긴 공약수를 반환
구현 예시
아래 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def gcdOfStrings(self, str1, str2):
if len(str1)<=len(str2):
temp = str1
else:
temp = str2
m = len(temp)
x = 1
res=[""]
while x<=m:
if m%x==0 and temp[:x] * (len(str1)//x) == str1 and temp[:x] * (len(str2)//x) == str2:
res.append(temp[:x])
x+=1
return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB","ABAB"))입력
"ABABAB" "ABAB"
출력
AB
더 효율적인 풀이: 수학적 GCD 활용
위 방식은 시간 복잡도가 O(n²)에 가까워 입력 크기가 커지면 비효율적일 수 있습니다. 다음과 같은 수학적 성질을 활용하면 훨씬 간결하고 빠르게 해결할 수 있습니다.
- str1 + str2 == str2 + str1이 성립하는 경우에만 두 문자열의 공약수가 존재합니다.
- 공약수가 존재한다면, 정답은 str1의 앞부분에서 gcd(len(str1), len(str2)) 길이만큼 잘라낸 문자열입니다.
import math
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
g = math.gcd(len(str1), len(str2))
return str1[:g]
print(Solution().gcdOfStrings("ABABAB", "ABAB")) # AB이 방법은 문자열 연결 일치 여부 검증과 두 길이의 최대공약수 계산만으로 답을 도출하므로, 코딩 테스트와 실무 모두에서 널리 사용되는 패턴입니다.