42 회문 판별과 N-gram 만들기
지금까지 문자열을 공부했으니 이번에는 문자열 응용편입니다. 문자열을 이용하여 회문을 판별하는 방법과 N-gram을 만드는 방법을 알아보겠습니다.
회문은 유전자 염기서열 분석에서 많이 쓰고, N-gram은 빅 데이터 분석, 검색 엔진에서 많이 쓰입니다. 특히 구글은 책들을 스캔해서 N-gram viewer를 만들었는데 사람들의 언어 패턴을 시대별로 분석하기도 했습니다.
42.1 회문 판별
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말합니다. 예를 들면 "level", "SOS", "rotator", "nurses run"과 같은 단어와 문장이 있지요.
그럼 문자열이 회문인지 판별하려면 어떻게 해야 할까요? 먼저 회문을 잘 살펴보면 첫 번째 글자와 마지막 글자가 같습니다. 그리고 안쪽으로 한 글자씩 좁혔을 때 글자가 서로 같으면 회문입니다.
즉, 가운데 문자 v를 기준으로 왼쪽과 오른쪽의 문자가 같습니다.
예제 코드를 보기 전에 스스로 고민해보고 코드를 작성해보세요. 고민하는 만큼 실력이 늡니다.
이제 문자열을 배열에 넣은 뒤 반복문으로 각 글자를 검사해보겠습니다.
palindrome.c
#define _CRT_SECURE_NO_WARNINGS // scanf 보안 경고로 인한 컴파일 에러 방지 #include <stdio.h> #include <string.h> #include <stdbool.h> int main() { char word[30]; // 단어를 저장할 배열 int length; // 문자열 길이 bool isPalindrome = true; // 회문 판별값을 저장할 변수, 초깃값은 true printf("단어를 입력하세요: "); scanf("%s", word); length = strlen(word); // 문자열의 길이를 구함 // 0부터 문자열 길이의 절반만큼 반복 for (int i = 0; i < length / 2; i++) { // 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면 if (word[i] != word[length - 1 - i]) { // 회문이 아님 isPalindrome = false; break; } } printf("%d\n", isPalindrome); // 회문 판별값 출력 return 0; }
소스를 컴파일하여 실행한 뒤 level을 입력하고 엔터 키를 누르세요.
실행 결과
단어를 입력하세요: level (입력) 1
문자열 "level"은 회문이므로 1이 출력됩니다. 만약 "hello"처럼 회문이 아닌 단어들을 입력하면 0이 출력됩니다.
실행 결과
단어를 입력하세요: hello (입력) 0
회문 판별에서 가장 중요한 부분은 문자열(단어)의 길이입니다. 왜냐하면 회문 판별은 문자열의 길이를 기준으로 하기 때문입니다.
length = strlen(word); // 문자열의 길이를 구함
이제 문자열 길이의 절반만큼만 반복하면서 왼쪽 문자와 오른쪽 문자들을 검사합니다. 만약 문자열의 길이가 5라면 5 / 2 = 2(정수 나눗셈)이므로 가운데 글자 바로 앞까지만 검사하게 됩니다.
반복문 안에서 왼쪽 문자 word[i]와 오른쪽 문자 word[length - 1 - i]를 비교하여 문자가 다르면 회문이 아니므로 isPalindrome에 false를 넣어주고 반복문을 끝냅니다. 어차피 회문이 아니기 때문에 더 검사할 필요가 없습니다.
// 0부터 문자열 길이의 절반만큼 반복 for (int i = 0; i < length / 2; i++) { // 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면 if (word[i] != word[length - 1 - i]) { // 회문이 아님 isPalindrome = false; break; } }
for 반복문의 i가 0부터 1씩 증가하므로 word[i]는 왼쪽에서 오른쪽으로 진행하고, word[length - 1 - i]는 오른쪽에서 왼쪽으로 진행합니다. 즉, 문자열의 마지막 문자는 word[length - 1]이므로 여기서 인덱스를 i만큼 계속 빼주면 오른쪽에서 왼쪽으로 진행하겠죠? (i가 커질 수록 더 왼쪽으로 옵니다)
