#문자열

프로그래머스 문제 중 문자열 분류에 해당하는 풀이를 다룬다. 현재 2개의 풀이가 있다.

프로그래머스 숫자 문자열과 영단어에서 왼쪽부터 숫자와 영단어를 구분해 정수로 바꾼다. 입력 순서를 유지하며 O(n) 시간에 값을 복원한다.

프로그래머스 스킬트리에서 선행 스킬에 포함된 문자만 추려 순서를 확인한다. 추출 결과가 선행 스킬 순서의 접두사인지 판정한다.

문자열 학습 가이드

필요한 주제만 펼쳐서 문자열의 인덱스, 구간 처리, 비교와 탐색 패턴을 익힌다.

문자열 기본 개념

문자열은 문자가 순서대로 나열된 자료다. 각 문자는 위치를 가지므로 인덱스, 부분 문자열의 시작과 끝, 반복 여부를 정확히 관리해야 한다.

입력의 대소문자, 공백, 특수문자를 그대로 비교할지 정규화할지 문제 조건에서 먼저 확인한다.

문자열 처리 패턴

문제의 목표가 문자열 변환인지, 문자 빈도인지, 특정 구간 탐색인지에 따라 상태를 다르게 유지한다.

두 포인터와 팰린드롬

앞과 뒤에서 동시에 확인할 수 있는 문제는 두 포인터로 전체 문자열을 반복해서 뒤집거나 부분 문자열을 만들지 않고 처리할 수 있다.

left, right = 0, len(text) - 1
while left < right:
    if text[left] != text[right]:
        return False
    left += 1
    right -= 1

공백과 대소문자를 무시하는 문제라면 비교 전에 정규화할 범위를 명확히 정해야 한다. 두 포인터가 교차하면 모든 비교가 끝난 것이다.

문자열 복잡도와 선택 기준

문자열 길이를 `n`이라고 할 때, 한 번 순회하는 처리는 `O(n)`입니다. 매 위치에서 문자열 전체를 다시 만들거나 검색하면 `O(n²)`이 될 수 있습니다.

Python 문자열은 불변이므로 반복해서 이어 붙이는 대신 리스트에 모은 후 `join`하는 방식이 긴 결과를 만들 때 유리하다.

자주 하는 실수