Unit 30. 회문 판별과 N-gram 만들기

이번에는 문자열 응용해서 회문을 판별하는 방법과 N-gram을 만드는 방법을 알아보겠습니다.

회문은 유전자 염기서열 분석에서 많이 쓰고, N-gram은 빅 데이터 분석, 검색 엔진에서 많이 쓰입니다. 특히 구글은 책들을 스캔해서 N-gram viewer를 만들었는데 사람들의 언어 패턴을 시대별로 분석하기도 했습니다.

30.1 회문 판별하기

회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말합니다. 예를 들면 "level", "SOS", "rotator", "nurses run"과 같은 단어와 문장이 있지요.

그럼 문자열이 회문인지 판별하려면 어떻게 해야 할까요? 먼저 회문을 잘 살펴보면 첫 번째 글자와 마지막 글자가 같습니다. 그리고 안쪽으로 한 글자씩 좁혔을 때 글자가 서로 같으면 회문입니다.

그림 30-1 회문
그림 30 1 회문

즉, 가운데 문자 v를 기준으로 왼쪽과 오른쪽의 문자가 같습니다.

예제 코드를 보기 전에 스스로 고민해보고 코드를 작성해보세요. 고민하는 만큼 실력이 늡니다.

이제 반복문으로 문자열의 각 문자를 검사해보겠습니다.

palindrome.py

word = input('단어를 입력하세요: ')
 
is_palindrome = True                 # 회문 판별값을 저장할 변수, 초깃값은 True
for i in range(len(word) // 2):      # 0부터 문자열 길이의 절반만큼 반복
    if word[i] != word[-1 - i]:      # 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
        is_palindrome = False        # 회문이 아님
        break
 
print(is_palindrome)                 # 회문 판별값 출력

소스 코드를 실행한 뒤 level을 입력하고 엔터 키를 누르세요.

실행 결과

단어를 입력하세요: level (입력)
True

문자열 'level'은 회문이므로 True가 출력됩니다. 만약 'hello'처럼 회문이 아닌 단어들을 입력하면 False가 출력됩니다.

실행 결과

단어를 입력하세요: hello (입력)
False

회문 판별에서 가장 중요한 부분은 문자열(단어)의 길이입니다. 왜냐하면 회문 판별은 문자열의 길이를 기준으로 하기 때문입니다. 즉, 문자열을 절반으로 나누어서 왼쪽 문자와 오른쪽 문자가 같은지 검사해야 합니다.

다음과 같이 반복을 할 때 문자열 길이의 절반만큼만 반복하도록 만듭니다. 예를 들어 문자열의 길이가 5라면 5 // 2 = 2(버림 나눗셈)이므로 가운데 글자 바로 앞까지만 검사하게 됩니다.

for i in range(len(word) // 2):      # 0부터 문자열 길이의 절반만큼 반복

반복문 안에서는 왼쪽 문자 word[i]와 오른쪽 문자 word[-1 - i]를 비교하여 문자가 다르면 회문이 아니므로 is_palindromeFalse를 넣어주고 break로 반복문을 끝냅니다. 어차피 회문이 아니므로 더 검사할 필요가 없습니다.

    if word[i] != word[-1 - i]:      # 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
        is_palindrome = False        # 회문이 아님
        break

for 반복문의 i가 0부터 1씩 증가하므로 word[i]는 왼쪽에서 오른쪽으로 진행하고, word[-1 - i]는 오른쪽에서 왼쪽으로 진행합니다. 즉, 문자열의 마지막 문자는 word[-1]이므로 여기서 인덱스를 i만큼 계속 빼주면 오른쪽에서 왼쪽으로 진행합니다. 이 부분은 파이썬에서 음수 인덱스를 지정하면 뒤에서부터 요소에 접근할 수 있다는 점을 이용한 것입니다. 음수 -1에서 숫자를 빼면 -2, -3, -4처럼 되므로 i가 커질 수록 더 왼쪽으로 옵니다.

그림 30-2 회문 판별 과정
그림 30 2 회문 판별 과정

참고로 word[-1 - i]word[-(1 + i)]와 같이 숫자를 i만큼 증가시킨 뒤 음수로 바꾸는 방식으로도 표현할 수 있습니다.