문자열 다루기

🎯 학습 목표

이 강을 마치면 파이썬 문자열이 수정 불가능(immutable)하다는 성질과 그것이 성능에 미치는 영향을 설명할 수 있습니다. 그리고 뒤집기·빈도 세기·회문 판별·부분 문자열 찾기 같은 코딩 테스트 단골 패턴을 복잡도를 의식하며 구현할 수 있게 됩니다.

문자열 문제는 출제 비중이 높습니다. 그리고 파이썬은 문자열 도구가 강력해서, 적절한 내장 기능을 알면 열 줄짜리 코드를 한 줄로 줄일 수 있습니다.

💡 문자열은 수정할 수 없다

파이썬 문자열의 가장 중요한 성질은 한 번 만들면 바꿀 수 없다는 것입니다. s[0] = "a" 같은 코드는 오류가 납니다.

그래서 "문자열을 수정한다"고 보이는 모든 연산은 사실 새 문자열을 만드는 것입니다. s.upper()도, s.replace("a", "b")도, s + "x"도 전부 새 객체를 만들어 돌려줍니다.

왜 이것이 성능 문제가 되는가

  s = ""
  for i in range(n):
      s += "x"          ← 매번 새 문자열을 만든다

  1번째: 길이 1 문자열 생성   (1글자 복사)
  2번째: 길이 2 문자열 생성   (2글자 복사)
  3번째: 길이 3 문자열 생성   (3글자 복사)
  ...
  n번째: 길이 n 문자열 생성   (n글자 복사)
  ─────────────────────────────────────────
  총 복사량 = 1+2+3+...+n ≈ n²/2  →  O(n²)

  ▲ 대안 : 리스트에 모았다가 한 번에 합친다

  parts = []
  for i in range(n):
      parts.append("x")   ← 상각 O(1)
  s = "".join(parts)      ← 전체 O(n)
  ─────────────────────────────────────────
  총 O(n)

  ※ CPython에는 특정 조건에서 += 를 최적화하는 경우가
    있지만, 항상 보장되는 동작은 아니다.
    join 을 쓰는 편이 안전하다.

이 하나만 알아도 문자열 문제에서 시간 초과를 크게 줄일 수 있습니다. 반복문 안에서 문자열을 더하지 말고, 리스트에 모았다가 join이 원칙입니다.

반대로 수정 불가능하다는 성질에는 장점도 있습니다. 문자열을 딕셔너리의 키나 집합의 원소로 쓸 수 있습니다. 값이 절대 변하지 않으므로 해시값이 안정적이기 때문입니다. 리스트는 수정 가능해서 키로 쓸 수 없습니다.

📖 자주 쓰는 문자열 도구와 복잡도

코딩 테스트에서 반복해서 등장하는 도구를 복잡도와 함께 정리하겠습니다. n은 문자열 길이입니다.

도구	하는 일	복잡도
s[i]	i번째 글자	O(1)
s[a:b]	부분 문자열 (새로 복사)	O(b-a)
s[::-1]	뒤집기	O(n)
s.split()	공백 기준으로 나누기	O(n)
"".join(lst)	리스트를 이어 붙이기	O(전체 길이)
t in s	부분 문자열 포함 여부	대략 O(n × m)
s.replace(a, b)	바꾼 새 문자열	O(n)
s.count(t)	등장 횟수	O(n × m)
s.strip()	양끝 공백 제거	O(n)

여기서 슬라이싱이 복사라는 점을 특히 조심해야 합니다. s[1:]을 반복문 안에서 쓰면 매번 새 문자열을 만들어 O(n²)이 됩니다. 3강 리스트에서 본 것과 같은 함정입니다.

문자와 숫자를 오갈 때 쓰는 함수도 알아 두면 좋습니다. ord("a")는 문자의 유니코드 번호를 주고, chr(97)은 반대로 문자를 돌려줍니다. 알파벳을 인덱스로 바꿀 때 ord(ch) - ord("a") 형태를 자주 씁니다.

💻 실전 예제 — 빈도 세기와 회문 판별

문자열 문제의 두 가지 대표 패턴을 구현해 보겠습니다.

from collections import Counter


def char_frequency(s):
    """각 글자가 몇 번 나오는지 센다 → O(n)"""
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1   # 없으면 0에서 시작
    return freq


def is_palindrome(s):
    """앞뒤가 같은 문자열인지 판별 (영숫자만, 대소문자 무시)"""
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True


def is_anagram(a, b):
    """두 문자열이 같은 글자로 이루어졌는지 → O(n)"""
    return Counter(a) == Counter(b)


text = "Never odd or even"
print(char_frequency("banana"))       # {'b': 1, 'a': 3, 'n': 2}
print(is_palindrome(text))            # True
print(is_anagram("listen", "silent")) # True

코드를 줄 단위로 보겠습니다.

• freq.get(ch, 0) — 딕셔너리에서 값을 꺼내되 키가 없으면 기본값 0을 줍니다. freq[ch]를 바로 쓰면 없는 키에서 오류가 납니다.
• for ch in s — 문자열을 순회하면 한 글자씩 나옵니다. 딕셔너리 조회·저장이 평균 O(1)이므로 전체는 O(n)입니다.
• [ch.lower() for ch in s if ch.isalnum()] — 리스트 컴프리헨션입니다. 영문자·숫자만 남기고(isalnum) 소문자로 바꿉니다. 공백과 문장부호를 걸러 냅니다.
• left, right = 0, len(cleaned) - 1 — 양 끝에서 출발하는 두 개의 인덱스입니다. 이 방식이 11강에서 배울 투 포인터입니다.
• while left < right — 두 인덱스가 만날 때까지 좁혀 갑니다. 비교 횟수는 n/2번이므로 O(n)입니다.
• Counter(a) == Counter(b) — Counter는 글자별 개수를 세어 주는 딕셔너리입니다. 두 Counter가 같으면 구성 글자가 같다는 뜻입니다. 각각 O(n)으로 세고 비교하므로 전체 O(n)입니다.

is_palindrome은 cleaned == cleaned[::-1]로도 쓸 수 있습니다. 한 줄로 짧지만 뒤집은 사본을 만들어 메모리를 O(n) 더 씁니다. 투 포인터 방식은 추가 메모리 없이 판별하고, 다르면 중간에 바로 멈춥니다. 두 방식의 차이를 이해하는 것이 이 예제의 목적입니다.

참고로 애너그램을 sorted(a) == sorted(b)로 판별하는 방법도 흔합니다. 이 방식은 정렬을 하므로 O(n log n)입니다. Counter 쪽이 O(n)으로 더 빠릅니다.

⚠️ 자주 하는 실수

첫째, 반복문 안에서 문자열을 더합니다. 이 강의 첫 주제이자 가장 흔한 실수입니다. 리스트에 모았다가 join을 습관으로 만드세요.

둘째, split()과 split(" ")을 같다고 생각합니다. 인자 없는 split()은 연속된 공백을 하나로 묶고 양끝 공백도 무시합니다. split(" ")은 공백 하나마다 잘라서 빈 문자열이 생깁니다. 입력에 공백이 여러 개 섞였다면 결과가 완전히 달라집니다.

셋째, 문자열을 리스트처럼 수정하려 합니다. 여러 글자를 바꿔야 한다면 list(s)로 리스트로 바꿔 작업한 뒤 "".join()으로 되돌리는 것이 정석입니다.

넷째, 대소문자·공백 처리를 빠뜨립니다. 회문·애너그램 문제는 "대소문자를 구분하는가", "공백을 무시하는가"가 조건에 명시돼 있습니다. 이 조건을 놓쳐 틀리는 경우가 매우 많습니다. 문제를 읽을 때 밑줄을 그어 두세요.

다섯째, in의 비용을 무시합니다. 부분 문자열 확인 t in s는 상수 시간이 아닙니다. 반복문 안에서 긴 문자열에 쓰면 부담이 커집니다. 여러 후보를 반복 확인해야 한다면 집합에 담아 두는 편이 낫습니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	문자열은 수정 불가능 — 모든 변경은 새 객체
2	반복문 안 +=는 O(n²) → join
3	슬라이싱은 복사다 (O(n))
4	빈도 세기는 딕셔너리 또는 Counter → O(n)
5	회문은 투 포인터로 추가 메모리 없이
6	애너그램은 Counter가 sorted보다 빠르다
7	split()과 split(" ")은 다르다

지금 해 볼 것은 " a b ".split()과 " a b ".split(" ")을 각각 출력해 보는 것입니다. 결과가 얼마나 다른지 보면 왜 조심해야 하는지 바로 알 수 있습니다.

다음 5강 「스택」부터는 본격적인 자료구조입니다. 배열의 "맨 뒤 추가·삭제는 O(1)"이라는 성질을 그대로 활용하는 구조이고, 괄호 검사·수식 계산 같은 단골 문제의 열쇠가 됩니다.

📚 참고 자료

• Text Sequence Type — str — Python 공식 문서
• collections.Counter — Python 공식 문서
• TimeComplexity — Python Wiki