두 개의 문자열 s와 t가 주어졌을 때, s에서 시작하여 두 문자열의 글자를 번갈아 가며 추가하는 방식으로 병합해야 합니다. 만약 s와 t의 길이가 같지 않다면, 남은 글자들은 병합된 문자열의 끝에 그대로 붙여주면 됩니다.
예를 들어 입력이 s = "major", t = "general"이라면 출력은 "mgaejnoerral"이 됩니다. t가 s보다 길기 때문에, 교대로 병합한 후 남은 부분인 "ral"을 마지막에 추가한 것입니다.
문제 해결 접근 방법
이 문제는 두 개의 포인터와 반복문을 사용하면 간단하게 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 두 인덱스 i와 j를 0으로 초기화하고, 결과를 저장할 빈 문자열 result를 준비합니다.
- i가 s의 길이보다 작고 j가 t의 길이보다 작은 동안, s[i]와 t[j]를 차례로 result에 이어 붙인 후 i와 j를 각각 1씩 증가시킵니다.
- s에 아직 남은 글자가 있다면, i가 s의 길이에 도달할 때까지 나머지 글자를 result에 추가합니다.
- t에 아직 남은 글자가 있다면, j가 t의 길이에 도달할 때까지 나머지 글자를 result에 추가합니다.
- 최종적으로 병합된 result를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
def solve(s, t): i = j = 0 result = "" while i < len(s) and j < len(t): result += s[i] + t[j] i += 1 j += 1 while i < len(s): result += s[i] i += 1 while j < len(t): result += t[j] j += 1 return result s = "major" t = "general" print(solve(s, t))
입력
"major", "general"
출력
mgaejnoerral
이 알고리즘의 시간 복잡도는 두 문자열 길이의 합에 비례하는 O(len(s) + len(t))이며, 공간 복잡도 역시 결과 문자열 크기만큼 필요하므로 O(len(s) + len(t))입니다.