리트코드 - 1768. Merge Strings Alternately

https://leetcode.com/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75

Merge Strings Alternately - LeetCode

오늘부터 리트코드 75를 풀 예정

입력받은 문자열 word1과 word2의 문자를 순서대로 번갈아가면서 합친 다음 한 문자열이 다른 문자열보다 긴 경우 병합된 문자열의 끝에 추가 문자를 추가하면 된다.

 

그러면 인덱스를 이동하면서 번갈아가면서 넣어주기만 하면 된다. 다만 해당 인덱스가 문자열의 인덱스를 out of range하지 않도록 조건을 지정해주어야 한다.

처음에 생각했던 풀이는 다음과 같다.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        cursor = 0
        merged_string = ""
        while cursor < len(word1) or cursor < len(word2): # O(n)
            if cursor < len(word1): # O(1)
                merged_string += word1[cursor] # O(1)
            if cursor < len(word2): # O(1)
                merged_string += word2[cursor] # O(1)
            cursor += 1
        return merged_string

 cursor를 만들어서 한 칸씩 이동시키고 각 문자열의 범위를 벗어나지 않으면 추가하고 아니면 제외하도록 하였다.

 

공간 복잡도

입력받은 문자열들을 순회하여야 하므로 최대 문자열의 길이가 n이라고 가정하면 O(n)이다.

 

시간 복잡도

공간복잡도는 문자열의 길이의 합 n만큼 저장할 수 있는 문자열 변수 merged_string을 할당하여야 하므로 O(n)이다.

 

하지만 테스트를 했을 때 런타임이 너무 안좋았다.

그 이유는 while cursor < len(word1) or cursor < len(word2): 코드 때문이라고 생각했다.

매 루프마다 cursor가 인덱스를 벗어나는지 확인하기 때문이다.

이를 위해 한 번의 연산으로 두 문자열의 최소 길이를 계산하고 반복문 안에서 추가적인 길이 계산을 하지 않는 방법을 생각했다.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        merged_string = ""
        for i in range(min(len(word1), len(word2))): # O(n)
            merged_string += word1[i] # O(1)
            merged_string += word2[i] # O(1)

        merged_string += word2[len(word1):] # O(1)
        merged_string += word1[len(word2):] # O(1)
        return merged_string

두 코드 모두 시간 복잡도는 O(n)이지만, 해당 코드가 반복문 내에서 수행되는 연산의 횟수가 더 적다

풀이 3.

+=는 Python에서 문자열을 불변 객체로 취급하기 때문에 매번 새로운 문자열을 생성하며, 이는 효율성이 낮을 수 있다.

join()은 최종 문자열을 한 번에 생성하기 때문에 더 효율적이다.

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        merged_list = []
        for i in range(max(len(word1), len(word2))): # O(n)
            if i < len(word1): # O(1)
                merged_list.append(word1[i]) # O(1)
            if i < len(word2): 
                merged_list.append(word2[i]) # O(1)
        return ''.join(merged_list) # O(n)