Merge Strings Alternately — 단일 루프로 `O(n + m)` 교차 병합

스터디·4분 읽기
#알고리즘
시리즈#알고리즘· 1/36편
전체 보기
  1. 01Merge Strings Alternately — 단일 루프로 `O(n + m)` 교차 병합읽는 중
  2. 02Increasing Triplet Subsequence — `O(n)` 시간, `O(1)` 공간으로 푸는 그리디 패턴
  3. 03Move Zeroes — 쓰기 포인터 하나로 `O(n)`/`O(1)` 제자리 재배치
  4. 04String Compression — 읽기/쓰기 포인터로 `O(n)`/`O(1)` 제자리 압축
  5. 05Product of Array Except Self — 나눗셈 없이 `O(n)`/`O(1)`로 나머지 곱 구하기
  6. 06Reverse Vowels of a String — 투 포인터 `O(n)` 스왑으로 모음만 뒤집기
  7. 07Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
  8. 08시간 복잡도와 공간 복잡도 완전 정복 — Big-O 표기법부터 실전 분석까지
  9. 09Greatest Common Divisor of Strings — `GCD`로 `O(n + m)` 문자열 최대 공약 패턴
  10. 10Container With Most Water — 투 포인터 `O(n)`로 최대 넓이 한 번에 찾기
  11. 11Is Subsequence — 투 포인터 `O(|s| + |t|)`로 부분 수열 판정
  12. 12Richest Customer Wealth — 2차원 배열에서 행 합의 최댓값 찾기
  13. 13Running Sum of 1d Array — 누적합의 가장 기본 형태
  14. 14Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기
  15. 15Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정
  16. 16Max Number of K-Sum Pairs — 정렬 `O(n log n)`에서 해시 `O(n)`까지 최대 페어 수 세기
  17. 17Ransom Note — 문자 개수로 문자열 구성 가능 여부 판정하기
  18. 18Middle of the Linked List — slow/fast 포인터로 중간 노드 찾기
  19. 19Max Consecutive Ones — 한 번의 스캔으로 가장 긴 1 구간 찾기
  20. 20Find Numbers with Even Number of Digits — 자릿수 개수의 짝수 여부 세기
  21. 21Merge Sorted Array — 뒤에서부터 채우는 제자리 병합
  22. 22Duplicate Zeros — 고정 길이 배열을 오른쪽에서부터 제자리 갱신하기
  23. 23Squares of a Sorted Array — 절댓값 기준 투 포인터로 `O(n)` 정렬 유지하기
  24. 24Valid Mountain Array — 올라갔다가 내려오는 배열 판별하기
  25. 25Check If N and Its Double Exist — 어떤 값과 그 두 배가 함께 있는지 확인하기
  26. 26Remove Duplicates from Sorted Array — 정렬 배열을 고유 값 구간으로 압축하기
  27. 27Remove Element — 앞쪽 유효 구간으로 압축하는 제자리 제거
  28. 28Replace Elements with Greatest Element on Right Side — 오른쪽 최댓값으로 바꾸기
  29. 29Sort Array By Parity — 짝수를 앞쪽으로 모으기
  30. 30Height Checker — 기대 순서와 다른 위치 세기
  31. 31Third Maximum Number — 세 변수로 상위 3개를 추적해 찾기
  32. 32Reorder Data in Log Files — 문자 로그만 정렬하고 숫자 로그는 순서 유지하기
  33. 33Valid Palindrome — 투 포인터로 영숫자만 비교하는 팰린드롬 판정
  34. 34Find All Numbers Disappeared in an Array — 음수 마킹으로 `O(n)`/`O(1)` 누락 숫자 찾기
  35. 35Most Common Word — 금지어를 제외하고 가장 자주 나온 단어 찾기
  36. 36Group Anagrams — 정렬 키와 문자 개수 키로 애너그램 묶기

두 문자열을 교대로 합치기, 어떤 문제인가요?

LeetCode 1768번 문제는 이렇게 주어집니다.

두 문자열 word1과 word2가 주어졌을 때, word1부터 시작하여 글자를 교대로 이어 붙인 문자열을 반환하세요. 한쪽 문자열이 더 길면, 남은 글자를 그대로 뒤에 붙입니다.

예시는 이렇습니다.

  • word1 = "abc", word2 = "pqr" → "apbqcr"
  • word1 = "ab", word2 = "pqrs" → "apbqrs"
  • word1 = "abcd", word2 = "pq" → "apbqcd"

제약은 간단합니다.

  • 1 <= word1.length, word2.length <= 100
  • 두 문자열 모두 소문자 영문으로만 구성

문제 자체는 단순하지만, 두 문자열의 길이가 다를 때 나머지를 어떻게 처리할 것인가가 구현의 분기점입니다. 이 글에서는 공통 구간을 분리하는 방식부터 단일 루프로 통합하는 방식까지 비교해 보겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 공통 구간과 나머지를 분리하는 접근

가장 직관적인 방법은 두 문자열이 겹치는 구간까지만 교대로 붙이고, 나머지는 한꺼번에 이어 붙이는 것입니다.

fun mergeAlternately(word1: String, word2: String): String {
    val sb = StringBuilder()
    val minLen = minOf(word1.length, word2.length)

    for (i in 0 until minLen) {
        sb.append(word1[i])
        sb.append(word2[i])
    }

    sb.append(word1.substring(minLen))
    sb.append(word2.substring(minLen))

    return sb.toString()
}

동작을 따라가 봅시다. word1 = "abcd", word2 = "pq"인 경우:

  • minLen = 2이므로 인덱스 0, 1까지 교대로 붙입니다 → "apbq"
  • word1.substring(2) = "cd", word2.substring(2) = "" → "apbqcd"

로직이 읽기 쉽고, "공통 구간"과 "나머지"가 코드 구조에서 명확히 분리됩니다. 다만 루프 하나와 substring 두 번으로 구성되어, 하나의 흐름으로 합칠 여지가 있습니다.

Phase 2. 단일 루프로 통합

공통 구간과 나머지를 나누지 않고, 더 긴 쪽의 길이만큼 루프를 돌면서 범위 안에 있는 쪽만 붙이는 방식입니다.

fun mergeAlternately(word1: String, word2: String): String {
    val sb = StringBuilder()

    for (i in 0 until maxOf(word1.length, word2.length)) {
        if (i < word1.length) sb.append(word1[i])
        if (i < word2.length) sb.append(word2[i])
    }

    return sb.toString()
}

같은 입력 word1 = "abcd", word2 = "pq"를 따라가 봅시다.

  • i = 0: word1[0] = 'a', word2[0] = 'p' → "ap"
  • i = 1: word1[1] = 'b', word2[1] = 'q' → "apbq"
  • i = 2: word1[2] = 'c', word2는 범위 밖 → "apbqc"
  • i = 3: word1[3] = 'd', word2는 범위 밖 → "apbqcd"

루프가 하나이고, 나머지 처리를 별도로 하지 않습니다. 범위 체크(i < length)가 공통 구간과 나머지 구간을 자연스럽게 통합합니다.

왜 StringBuilder를 쓰나요?

Kotlin(JVM)에서 String은 불변입니다. + 연산으로 문자열을 반복 이어 붙이면, 매번 새로운 String 객체가 생성되고 기존 내용을 복사합니다. 길이 n짜리 문자열을 한 글자씩 n번 이어 붙이면 복사량이 1 + 2 + ... + n = O(n²)이 됩니다.

StringBuilder는 내부 버퍼를 두고 append할 때 버퍼가 충분하면 복사 없이 바로 추가합니다. 전체 append 비용이 O(n + m) 으로 유지됩니다.

이 문제의 제약(length <= 100)에서는 차이가 체감되지 않지만, 문자열을 반복 조합하는 패턴에서 StringBuilder를 쓰는 것은 기본 습관으로 가져가는 것이 좋습니다.

두 풀이를 다시 비교

풀이 시간 공간 특징
공통 구간 분리 (minOf) O(n + m) O(n + m) 구간이 명시적으로 나뉘어 읽기 쉬움
단일 루프 (maxOf) O(n + m) O(n + m) 루프 하나로 통합, 분기가 단순

두 풀이 모두 시간·공간 복잡도는 동일합니다. n은 word1.length, m은 word2.length이고, 결과 문자열 자체가 n + m 길이이므로 공간을 더 줄일 수는 없습니다.

마무리

  1. 두 문자열의 길이가 다를 때 핵심은 "나머지 처리" — 공통 구간을 분리하든, 범위 체크로 통합하든 이 부분을 빠뜨리지 않는 것이 중요합니다
  2. 단일 루프 + 범위 체크 패턴은 길이가 다른 두 시퀀스를 병합할 때 자주 쓰입니다 — 이 문제에서는 maxOf(len1, len2)까지 돌면서 각각 범위 안에 있는지만 확인하면 됩니다
  3. 문자열 반복 조합에는 StringBuilder — 불변 String의 + 연산은 매번 복사가 발생하므로, 루프 안에서 문자열을 조합할 때는 StringBuilder를 사용하는 습관이 필요합니다
← 목록으로
공유
다음 편

Increasing Triplet Subsequence — `O(n)` 시간, `O(1)` 공간으로 푸는 그리디 패턴

다음으로 읽어볼 글

스터디

Group Anagrams — 정렬 키와 문자 개수 키로 애너그램 묶기

애너그램 문자열을 같은 그룹으로 묶는 LeetCode 49번, 정렬된 문자열을 키로 쓰는 풀이부터 문자 개수 배열을 해시 키로 바꾸는 `O(n * k)` 풀이까지 정리합니다.

#알고리즘
·9분
스터디

Most Common Word — 금지어를 제외하고 가장 자주 나온 단어 찾기

문단에서 금지어를 제외하고 가장 많이 등장한 단어를 찾는 LeetCode 819번, 문장 부호 제거와 소문자 정규화, 해시 카운팅 풀이를 정리합니다.

#알고리즘
·12분
스터디

Find All Numbers Disappeared in an Array — 음수 마킹으로 `O(n)`/`O(1)` 누락 숫자 찾기

1부터 n까지의 숫자 중 배열에 나타나지 않은 값을 찾는 LeetCode 448번, 완전 탐색부터 존재 배열, 음수 제자리 마킹 풀이까지 정리합니다.

#알고리즘
·9분