쉬움
Valid Palindrome
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 회문인가(s):2 글자 = s에서 영숫자만 남겨 소문자로3 왼 = 0, 오 = 글자수 - 14 동안 왼 < 오:5 만약 글자[왼] ≠ 글자[오]:6 반환 거짓7 왼 = 왼 + 1, 오 = 오 - 18 반환 참
변수
- 왼
- 0
- 오
- 4
- 글자수
- 5
1 / 4영숫자만 남겨 소문자로 맞추고, 양끝에 포인터를 둡니다.
문자를 정리한 뒤 양끝에서 안쪽으로 마주 보며 같은지 확인한다.
왜 헷갈리는가
'뒤집어서 원본과 비교'해도 되지만 그건 O(n) 추가 메모리를 쓴다. 투포인터는 제자리에서 O(1) 공간으로 끝나고, 무엇보다 '어디서 처음 어긋났는지'를 보여 준다. 또 무엇을 '글자'로 볼지(공백·문장부호·대소문자) 정의가 문제의 절반이다.
핵심 아이디어
대칭이면 양끝이 항상 같아야 한다. 왼쪽·오른쪽 포인터를 좁혀 오며 마주 본 쌍을 비교하고, 하나라도 다르면 즉시 아니다.
복잡도
시간 O(n)·공간 O(1). 뒤집어 비교하는 방식(O(n) 공간)보다 메모리 효율적이다.
실무에서 어디에 쓰나
'양끝에서 좁혀 오며 대칭·조건을 확인'하는 패턴은 문자열 검증 전반에 쓰인다.
- 입력 검증: 회문 코드·대칭 토큰·팰린드롬 해시 확인
- 정규화 파이프라인: 비교 전 영숫자만 남기고 소문자화(검색·중복제거 전처리)
- DNA/바이오: 역상보 서열의 대칭 구간 탐색의 기초 형태
- 투포인터 일반화: 두 배열 병합·구간 좁히기의 입문 패턴
흔한 실수
무엇을 글자로 볼지(공백·기호·대소문자)를 정의하지 않아 오판. 유니코드 정규화 누락.
기억할 것
- 대칭 = 양끝이 같다.
- 투포인터는 O(1) 공간.
- '글자' 정의가 문제의 절반.
- 투포인터 패턴의 입문.