Ch.2 배열과 문자열

문자열 조작 — Reverse, Palindrome, Anagram

문자열의 배열적 특성을 이해하고 in-place 조작 기법을 익힌다Palindrome과 Anagram 판별을 효율적으로 구현한다

문자열은 결국 문자의 배열이다

"racecar"를 뒤집어도 "racecar"입니다. "listen"의 글자를 재배열하면 "silent"가 되죠.

문자열 문제는 배열 문제와 무엇이 다를까?

문자열 = 문자 배열입니다. 배열 기법(Two Pointer, 해시)을 그대로 적용할 수 있습니다!

lightbulb

핵심 개념

Palindrome

앞뒤로 읽어도 같은 문자열 (예: racecar)

Anagram

글자 구성이 같은 두 문자열 (예: listen ↔ silent)

article

핵심 내용

프로그래밍에서 문자열은 문자(char)의 배열입니다

Two Pointer로 문자열을 제자리에서 뒤집어봅시다. 추가 메모리 없이 O(n)!

def reverse_string(s: list[str]) -> None:
    """in-place 뒤집기 — 추가 메모리 O(1)"""
    left, right = 0, len(s) - 1
    
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# 테스트
chars = ['h', 'e', 'l', 'l', 'o']
reverse_string(chars)
print(chars)  # ['o', 'l', 'l', 'e', 'h']

Palindrome 판별도 Two Pointer! 양 끝에서 좁혀오며 비교합니다

def is_palindrome(s: str) -> bool:
    """영문·숫자만 비교, 대소문자 무시"""
    s = ''.join(c.lower() for c in s if c.isalnum())
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

Anagram = 글자 구성(빈도)이 같은 두 문자열 Counter(해시맵)로 O(n) 판별!

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))   # False

# Counter 없이 직접 구현
def is_anagram_manual(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True

Palindrome 판별의 시간복잡도는?

"listen"과 "silent"는 Anagram이다

Anagram 판별에 가장 효율적인 자료구조는 ____(해시맵)이다.

Anagram 판별에 가장 효율적인 자료구조는 ____(해시맵)이다.

문자열 조작 마스터

key

핵심 용어

🔄

Reverse

문자열을 뒤집기 (Two Pointer 활용)

🪞

Palindrome

앞뒤로 읽어도 같은 문자열

🔀

Anagram

글자 구성(빈도)이 동일한 문자열 쌍

edit_note

정리 노트

문자열 = 문자 배열

3대 문자열 기법

Reverse
Two Pointer로 in-place 뒤집기 — O(n), O(1) 공간
Palindrome
양 끝 비교 Two Pointer — O(n)
Anagram
Counter(해시맵) 빈도 비교 — O(n)
★

면접 포인트: 문자열 문제에서 '이건 결국 배열 문제입니다'라고 말할 수 있어야 합니다!

image

시각 자료

다이어그램: ds-d13
다이어그램: ds-d14
check_circle

핵심 정리

  • 1문자열 = 문자 배열, 배열 기법 그대로 적용
  • 2Reverse: Two Pointer in-place O(n)
  • 3Palindrome: 양 끝 비교 O(n)
  • 4Anagram: Counter 해시맵 O(n)

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작