문자열 인터리빙이란?
두 개의 문자열 s와 t가 주어졌을 때, 첫 번째 문자열 s부터 시작하여 두 문자열의 문자를 번갈아 가며 교차 배치하는 새로운 문자열을 만드는 문제를 생각해 봅시다. 만약 한쪽 문자열에 문자가 남아 있다면, 남은 문자들은 결과 문자열의 끝에 그대로 추가됩니다.
예를 들어, 입력이 s = "abcd", t = "pqrstu"라면 출력은 "apbqcrdstu"가 됩니다. 두 문자열 중 t가 더 길기 때문에, 앞부분은 'a', 'p', 'b', 'q', 'c', 'r', 'd' 순서로 교차되고, 남은 "stu"는 마지막에 붙게 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다:
- 결과를 저장할 빈 문자열 res를 초기화합니다.
- 인덱스 변수 i를 0으로 설정합니다.
- 두 문자열 길이 중 더 짧은 값을 m으로 저장합니다.
- i가 m보다 작은 동안 반복하면서, res에 s[i]와 t[i]를 차례로 이어 붙인 후 i를 1씩 증가시킵니다.
- 반복이 끝나면, 각 문자열에서 인덱스 i부터 끝까지 남은 부분(s[i:]와 t[i:])을 res 뒤에 이어 붙여 반환합니다.
구현 예제
class Solution:
def solve(self, s, t):
res = ""
i = 0
m = min(len(s), len(t))
while i < m:
res += s[i] + t[i]
i += 1
return res + s[i:] + t[i:]
ob = Solution()
s = "abcd"
t = "pqrstu"
print(ob.solve(s, t))
입력
"abcd", "pqrstu"
출력
apbqcrdstu
시간 복잡도 분석
이 알고리즘은 두 문자열의 모든 문자를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n + m)입니다. 여기서 n과 m은 각각 문자열 s와 t의 길이입니다. 공간 복잡도 역시 결과 문자열을 저장하기 위해 O(n + m)이 필요합니다.
참고로, 위 구현에서는 문자열 연결 연산(+=)을 사용했는데, Python에서 문자열은 불변(immutable)이므로 매번 새로운 문자열 객체가 생성됩니다. 성능이 중요한 경우에는 리스트에 문자를 추가한 후 마지막에 join() 메서드로 합치는 방식이 더 효율적입니다.