Problem: Merge K Sensor Data Streams Alternately

# Description

You are building a data ingestion pipeline for a smart farm system. You receive log data from K different edge sensors. Each sensor transmits its logs as a string. To prevent traffic bottlenecks and maintain a balanced chronological sampling across all sensors, you need to merge these K log strings alternately, character by character, in the order the sensors are given. If a sensor's log is exhausted (shorter than others), you must skip it and continue merging the remaining active sensors' logs. Return the final merged log string.

Example 1:

• Input: logs = ["abc", "pqr", "xyz"]
• Output: "apxbqycrz"
• Explanation:

logs[0]: a   b   c
logs[1]:   p   q   r
logs[2]:     x   y   z
merged : a p x b q y c r z

---

 

**Example 2:**
*   **Input:** `logs = ["ab", "pqrst", "xy"]`
*   **Output:** `"apxbqyrst"`
*   **Explanation:**
    ```text
    logs[0]: a   b
    logs[1]:   p   q   r   s   t
    logs[2]:     x   y 
    merged : a p x b q y r s t

---

Constraints:

• 1 < K <= 10^4
• 1 <= logs[i].length <=10^4
• The total number of characters across all logs does not exceed 10^7.
• logs[i] consists of lowercase English letters.

---

# Key Points

위의 Description을 살펴보면, K개의 데이터 스트림 처리로 Scale-up 되었을 때 그 중요성이 극대화되거나 혹은 구조 자체가 바뀌어야 하는 핵심 포인트를 인지하고 있어야 한다. 세 가지 포인트를 코드 작성 전에 파악해야 한다. 첫 번째로는 배열로 나누지 않고 문자열 자체로 접근해야 한다는 점이다. 센서의 개수와 길이 (여기서는 문자열)가 리스트로 변환하는 순간 메모리 할당이 늘어나기 때문에 현재 있는 문자열 그대로 다뤄야 한다. 두 번째는 메모리 효율성을 위한 "join()" 메서드를 사용하는 것이다. +=와 같은 연산자로도 코드 작성이 가능하지만 메모리 재할당 과정에서 효율이 떨어지기 때문에 "join()"을 활용하는 것이 좋다. 세 번째로는 더 짧은 길이를 찾고 남은 부분을 슬라이싱으로 붙이는 것이다. 현재 문제에서 설정된 조건이 K개 (미지수)이기 때문에 센서가 멈춰도 나머지 K-1 개의 센서들은 계속 번갈아 가며 돌아가야 한다. 따라서 먼저 짧은 길이를 찾아서 산출해 주고 나머지 단순 슬라이싱이 되게끔 설정한다는 개념을 이해하고 있으면 좋다.

---

# Answers

나는 문제를 풀때 두 가지 성향을 고려해서 결과를 고르곤 한다. 솔직히 둘 중에 기억나는 걸로 골라서 쓰면 된다. 뭔가 코테가 예전에는 쉬웠는데, 요즘에는 AI로 코딩을 하다 보니, 기억이 잘 나지 않을 때가 많아진 건 같다.

 

아무튼 본론으로 돌아와서, 첫번째 답은 정석에 해당하는 답이다. 한마디로 큐(Queue)를 활용해서 라운드 로빈 스케줄링을 그대로 사용한 알고리즘에 해당한다. 데이터 엔지니어링 파이프라인의 가장 기초일 수 있다고 볼 수 있다. 두 번째는 답은 zip_longest를 활용한 데이터 트랜스포메이션이다. 내가 애용하는 방식인데, 한마디로 실무에서 효율적 설계를 한 방식이며, 데이터 전처리 코드를 짤 때 사용하는 C엔진을 활용한 코드이다. 그냥 한마디로 짧고 수정하기 용이하다이다.

---

from collections import deque

class Solution:
    def mergeKLogs(self, logs: list[str]) -> str:
        # 1. 큐에 (문자열, 현재 읽고 있는 인덱스)를 묶어서 튜플로 저장합니다.
        # 빈 문자열은 애초에 큐에 넣지 않습니다.
        q = deque([(s, 0) for s in logs if s])
        merged = []
        
        # 2. 큐가 완전히 빌 때까지 반복합니다.
        while q:
            # 큐의 맨 앞에서 하나를 꺼냅니다 (FIFO)
            s, idx = q.popleft()
            
            # 현재 인덱스의 문자를 결과 배열에 추가합니다
            merged.append(s[idx])
            
            # 해당 문자열에 아직 읽을 문자가 남아있다면, 인덱스를 +1 해서 큐의 '맨 뒤'로 다시 보냅니다.
            if idx + 1 < len(s):
                q.append((s, idx + 1))
                
        # 3. 1,000만 개의 문자를 단번에 결합하여 반환합니다.
        return "".join(merged)

---

from itertools import zip_longest

class Solution:
    def mergeKLogs(self, logs: list[str]) -> str:
        # 1. *logs를 통해 K개의 문자열을 zip_longest에 언패킹(Unpacking)하여 넘깁니다.
        # 2. 짧은 문자열은 fillvalue=""(빈 문자열)로 채워집니다.
        # 3. 이중 컴프리헨션을 사용해 빈 문자열이 아닌 것만 필터링하여 결합합니다.
        
        return "".join(char for chars in zip_longest(*logs, fillvalue="") for char in chars if char)

---

"둘 코드의 차이점이 뭔가요?"라고 물어본다면 효율성이라고 볼 수 있다. 아무래도 문자열을 처리하는 속도면에서 zip_longest를 사용한 후자가 차이가 나타난다. 당연히 해당 두 예제 코드만으로만 비교하면 큰 차이가 보이지 않을 수 있지만 더 복잡하고 많은 양의 데이터를 처리한다면 그 차이가 나타나기 시작한다. 그럼에도 전자의 큐를 사용한 코드를 실무에서 사용하는 이유는 개발자들 사이에서 문제를 파악하고 유지보수하기가 훨씬 쉽기 때문이다. 한마디로 문제가 풀어서 있으니 읽고 파악하기 용이하다. 하지만 이제는 AI시대이니 개인적으로 복잡해지더라도 효율성 위주로 가지 않을까 생각한다.

---