28.1 회문 판별하기
Unit 28. 회문 판별과 N-gram 만들기
이번에는 문자열을 응용해서 회문을 판별하는 방법과 N-gram을 만드는 방법을 알아보겠습니다.
회문은 유전자 염기서열 분석에서 많이 쓰고, N-gram은 빅 데이터 분석, 검색 엔진에서 많이 쓰입니다. 특히 구글은 책들을 스캔해서 N-gram viewer를 만들었는데 사람들의 언어 패턴을 시대별로 분석하기도 했습니다.
28.1 회문 판별하기
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말합니다. 예를 들면 "level", "SOS", "rotator", "nurses run"과 같은 단어와 문장이 있지요.
그럼 문자열이 회문인지 판별하려면 어떻게 해야 할까요? 먼저 회문을 잘 살펴보면 첫 번째 글자와 마지막 글자가 같습니다. 그리고 안쪽으로 한 글자씩 좁혔을 때 글자가 서로 같으면 회문입니다.
즉, 가운데 문자 v를 기준으로 왼쪽과 오른쪽의 문자가 같습니다.
예제 코드를 보기 전에 스스로 고민해보고 코드를 작성해보세요. 고민하는 만큼 실력이 늡니다.
28.1.1 반복문으로 문자 검사하기
이제 반복문으로 문자열의 각 문자를 검사해보겠습니다.
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_palindrome에 False를 넣어주고 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가 커질 수록 더 왼쪽으로 옵니다.
참고로 word[-1 - i]는 word[-(1 + i)]와 같이 숫자를 i만큼 증가시킨 뒤 음수로 바꾸는 방식으로도 표현할 수 있습니다.
28.1.2 시퀀스 뒤집기로 문자 검사하기
반복문으로 문자열의 각 문자를 일일이 비교하려니 다소 번거롭습니다. 그럼 좀 더 간단한 방법은 없을까요? 회문은 시퀀스 객체의 슬라이스를 활용하면 간단하게 판별할 수 있습니다.
palindrome_slice.py
word = input('단어를 입력하세요: ') print(word == word[::-1]) # 원래 문자열과 반대로 뒤집은 문자열을 비교
실행 결과
단어를 입력하세요: level (입력) True 단어를 입력하세요: hello (입력) False
word == word[::-1] 한 줄로 간단하게 끝났습니다. 너무 쉽죠? word[::-1]은 문자열 전체에서 인덱스를 1씩 감소시키면서 요소를 가져오므로 문자열을 반대로 뒤집습니다. 회문은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 문자열이므로 원래 문자열 word와 뒤집은 문자열 word[::-1]이 같으면 회문입니다.
28.1.3 리스트와 reversed 사용하기
사실 파이썬에서는 이 방법이외에도 다양한 방법으로 회문을 판별할 수 있습니다. 다음과 같이 반복 가능한 객체의 요소 순서를 반대로 뒤집는 reversed를 사용해도 됩니다.
>>> word = 'level' >>> list(word) == list(reversed(word)) True
list에 문자열을 넣으면 문자 하나 하나가 리스트의 요소로 들어갑니다. 여기서 reversed로 문자열을 반대로 뒤집어서 list에 넣으면 문자 순서가 반대로 된 리스트를 구할 수 있죠?
>>> list(word) ['l', 'e', 'v', 'e', 'l'] >>> list(reversed(word)) ['l', 'e', 'v', 'e', 'l']
이 두 리스트를 ==로 비교하면 문자열이 회문인지 판별할 수 있습니다.
28.1.4 문자열의 join 메서드와 reversed 사용하기
리스트와 reversed를 사용하는 방법 말고도 문자열의 join 메서드를 사용해서 회문을 판별할 수도 있습니다.
>>> word = 'level' >>> word == ''.join(reversed(word)) True
join은 구분자 문자열과 문자열 리스트의 요소를 연결합니다. 여기서는 빈 문자열 ''에 reversed(word)의 요소를 연결했으므로 문자 순서가 반대로 된 문자열을 얻을 수 있습니다. 즉, join은 요소 사이에 구분자를 넣지만 빈 문자열 ''을 활용하여 각 문자를 그대로 연결하는 방식입니다.
>>> word 'level' >>> ''.join(reversed(word)) 'level'
이 두 문자열을 ==로 비교하면 문자열이 회문인지 판별할 수 있습니다.