PostsSeriesLabsAlgo

문자열

문자열과 회문

뒤집어도 같은 말

먼저 맞혀 보세요. 앞에서 읽으나 뒤에서 읽으나 같은 말인지 알아내려고 합니다

「아버지」를 뒤집어 읽어도 같은 말일까요?

견준 쌍 0

기 ↔ 기 → 가운데 러기러기는 같은 한 쌍만 견주면 끝났습니다. 가운데 글자는 짝이 없어도 됩니다.

앞에서 읽으나 뒤에서 읽으나 같은 말 = 회문(palindrome)

  • s[0] — 글자마다 0번부터 번호가 있다. 맨 앞 글자가 0번이다
  • len(s) — 글자 수. 「기러기」는 3이고 마지막 글자는 s[len(s) - 1] 또는 s[-1] 이다
  • 한 줄 방법 — s == s[::-1] 은 글자를 거꾸로 뒤집은 새 문자열과 같은지 본다
한 쌍씩 견주기 · 모두 같은 100만 글자17.2ms
뒤집어 비교 · 모두 같은 100만 글자0.49ms
한 쌍씩 견주기 · 첫 글자부터 다른 100만 글자0.003ms
뒤집어 비교 · 첫 글자부터 다른 100만 글자0.41ms
Python 3.14 에서 직접 잰 값이고 컴퓨터마다 다릅니다. 한 줄 방법은 C 로 돌아서 회문일 때 더 빠릅니다. 한 쌍씩 견주는 쪽은 첫 쌍부터 다르면 바로 멈춥니다.

한 쌍씩 안쪽으로 좁히는 방법은 앞에서 본 투 포인터와 같습니다.

짝은 앞에서 i번째와 뒤에서 i번째다

  • 짝 — 맨 앞과 맨 뒤, 그다음 앞에서 둘째와 뒤에서 둘째. 바깥에서 안쪽으로 한 쌍씩 짝이 된다
  • 가운데 — 두 끝이 만나면 끝난다. 글자 수가 홀수면 가운데 한 글자는 짝이 없어도 된다
  • 하나라도 다르면 — 거기서 바로 멈춘다. 나머지 쌍은 볼 필요가 없다

코드는 양끝 번호 둘이 전부다

단어를 골라 다음을 눌러 보세요. 짝이 같으면 두 끝이 안쪽으로 한 칸씩 가고 다르면 5번 줄에서 끝납니다.

다음을 눌러 한 줄씩 넘겨 보세요

left = 0 right = 2

is_palindrome.py
  1. 1def is_palindrome(s):
  2. 2 left, right = 0, len(s) - 1
  3. 3 while left < right:
  4. 4 if s[left] != s[right]:
  5. 5 return False
  6. 6 left += 1
  7. 7 right -= 1
  8. 8 return True
0 / 7
  • left · right — 지금 견주는 앞 글자와 뒤 글자의 번호
  • s[left] != s[right] — 짝이 다르면 5번 줄에서 False 로 끝난다
  • left < right — 두 끝이 만나거나 엇갈리면 반복이 끝나고 True

abca 에 같은 코드를 돌립니다. 몇 쌍을 견주고 끝날까요?

문자열에서 틀리는 자리

  • 문자열은 못 바꾼다 — s[0] = 'a' 는 TypeError: 'str' object does not support item assignment. 글자를 고치려면 새 문자열을 만든다
  • 문장은 먼저 거른다 — A man, a plan, a canal: Panama 는 그대로 False 다. 대문자는 소문자로 바꾸고 공백과 기호는 걸러 amanaplanacanalpanama 로 만들어야 True 다. lower() 와 isalnum() 을 쓴다
  • left <= right — 써도 결과는 같다. a·b·c 로 만든 6글자 이하의 모든 문자열을 돌려 확인했다. 가운데 글자를 자기 자신과 한 번 더 견줄 뿐이다
  • 빈 문자열과 한 글자 — 견줄 쌍이 없어서 둘 다 True 다. 반복문이 한 번도 돌지 않는다
  • 한글의 길이 — len('가') 는 1이다. 자모로 풀어 쓴 문자열(NFD)에서는 가 가 2, 각 이 3이 되어 길이가 달라진다

문제에서 이 말이 보이면

앞뒤로 읽어도 같다양끝에서 안쪽으로 좁힌다문자열을 뒤집거나 잘라 비교한다

다음 장에서는 유클리드가 2300년 전에 푼 최대공약수를 봅니다.