[Algorithm] 주어진 문자열이 회문(Palindrome)인지 확인하기
주어진 문자열이 palindrome(회문)인지 확인하는 코드를 작성해보자
환경 및 선수조건
- Python
- C++
Palindrome(회문)이란?
Palindrome(회문)은 문자열을 거꾸로 해도 원래의 문자열과 같은 문자열인 특징을 가지고 있는 문자열을 가리키는 말입니다.- 예시: 토마토, abdba, 토마토맛토마토, 1234567654321
코드
- 시간복잡도:
O(n)
C
#include <stdio.h>
#include <string.h>
int is_palindrome(char * s){
int len = strlen(s);
int left = 0;
int right = len-1;
// 왼쪽과 오른쪽을 하나씩 가운데로 향하면서 비교
// (right - left) > 1
// [홀수 길이의 경우] 가운데 원소만 남겨두거나
// [짝수 길이의 경우] "left + 1==right"일 때까지!
while ( (right - left) > 1 ) {
if( s[right] != s[left] ){
return 0;
}
left += 1;
right -= 1;
}
return 1;
}
int main (){
char * palindrome = "abcdcba";
char * non_palindrome = "abcdefg";
printf("%d\n", is_palindrome(palindrome));
printf("%d\n", is_palindrome(non_palindrome));
return 0;
}
C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool is_palindrome(string s){
string s_reverse = s;
reverse(s_reverse.begin(), s_reverse.end());
return s == s_reverse ? true : false;
}
int main (){
string s1 = "abcde1edcba";
string s2 = "asdlkfjaw;oefjao;iwefja;ow";
cout << is_palindrome(s1) << '\n';
cout << is_palindrome(s2) << '\n';
return 0;
}
Python
def is_palindrome(s):
return s == s[::-1]
s1 = "abcde1edcba"
s2 = "fjaw;"
print(is_palindrome(s1))
print(is_palindrome(s2))