회문 (Palindrome, 回文, 팰린드롬)

 

 

회문

Palindrome, 回文

---

 

 

회문(回文) 또는 팰린드롬(palindrome)은 앞에서 읽으나 거꾸로 읽으나 같은 문장이나 낱말을 뜻합니다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다..고 하지만 알고리즘 문제를 풀 때에는 고려하는 경우도 있으므로 문제 조건을 잘 읽어보는 것이 좋습니다.

 

 

 

한국어에서의 예

- 기러기

- 다 간다 이 일요일 일요일이 다 간다

 

 

영어에서의 예

- race car

- A man, a plan, a caret, a ban, a myriad, a sum, a lac, a liar, a hoop, a pint, a catalpa, a gas, an oil, a bird, a yell, a vat, a caw, a pax, a wag, a tax, a nay, a ram, a cap, a yam, a gay, a tsar, a wall, a car, a luger, a ward, a bin, a woman, a vassal, a wolf, a tuna, a nit, a pall, a fret, a watt, a bay, a daub, a tan, a cab, a datum, a gall, a hat, a fag, a zap, a say, a jaw, a lay, a wet, a gallop, a tug, a trot, a trap, a tram, a torr, a caper, a top, a tonk, a toll, a ball, a fair, a sax, a minim, a tenor, a bass, a passer, a capital, a rut, an amen, a ted, a cabal, a tang, a sun, an ass, a maw, a sag, a jam, a dam, a sub, a salt, an axon, a sail, an ad, a wadi, a radian, a room, a rood, a rip, a tad, a pariah, a revel, a reel, a reed, a pool, a plug, a pin, a peek, a parabola, a dog, a pat, a cud, a nu, a fan, a pal, a rum, a nod, an eta, a lag, an eel, a batik, a mug, a mot, a nap, a maxim, a mood, a leek, a grub, a gob, a gel, a drab, a citadel, a total, a cedar, a tap, a gag, a rat, a manor, a bar, a gal, a cola, a pap, a yaw, a tab, a raj, a gab, a nag, a pagan, a bag, a jar, a bat, a way, a papa, a local, a gar, a baron, a mat, a rag, a gap, a tar, a decal, a tot, a led, a tic, a bard, a leg, a bog, a burg, a keel, a doom, a mix, a map, an atom, a gum, a kit, a baleen, a gala, a ten, a don, a mural, a pan, a faun, a ducat, a pagoda, a lob, a rap, a keep, a nip, a gulp, a loop, a deer, a leer, a lever, a hair, a pad, a tapir, a door, a moor, an aid, a raid, a wad, an alias, an ox, an atlas, a bus, a madam, a jag, a saw, a mass, an anus, a gnat, a lab, a cadet, an em, a natural, a tip, a caress, a pass, a baronet, a minimax, a sari, a fall, a ballot, a knot, a pot, a rep, a carrot, a mart, a part, a tort, a gut, a poll, a gateway, a law, a jay, a sap, a zag, a fat, a hall, a gamut, a dab, a can, a tabu, a day, a batt, a waterfall, a patina, a nut, a flow, a lass, a van, a mow, a nib, a draw, a regular, a call, a war, a stay, a gam, a yap, a cam, a ray, an ax, a tag, a wax, a paw, a cat, a valley, a drib, a lion, a saga, a plat, a catnip, a pooh, a rail, a calamus, a dairyman, a bater, a canal - Panama! (파나마 운하 건설 당시 사용되었던 회문)

 

 

 

 

 

 

그렇다면 이러한 회문을 판별하는 알고리즘은 어떻게 구현할 수 있을까요?

그냥 생각만 해봐도 매우 쉽..네요 ㅎㅎ;;

 

아래의 코드들은 다 주관적으로 짠 것이라.... 그저 저의.. 방법... 비효율적일 수 있는 제 방법.. 일 뿐이니.. 참고만 해주시길 바래요..ㅎㅎ

 

 

---

 

가장 간단하게는..

위와 같은 회문을 검사한다고 할 때, 그냥 앞과 뒤를 하나씩 비교해주면 될 듯 합니다.

그러니 반까지만 확인을 하면 되겠죠?   

 

조건

- 대소문자 구분한다. (r과 R은 다르다)

- 띄어쓰기 구분한다. ('rr r'은 회문이 아니다)

#include<iostream>
#include<string>
using namespace std;
int main(){
	string s;
	getline(cin, s);

	int len = s.length();
	int halflen = len/2;

	for (int i = 0; i < halflen; i++){
		if (s.at(i) != s.at(len - 1 - i)){
			cout << "NOT Palindrome" << endl;
			return 0;
		}
	}

	cout << "Palindrome"<<endl;

	return 0;
}

 

 

 

 

 

 

 

---

 

두 번째로, 대소문자를 구분하지 않는 방법입니다.

저같은 경우는 걍 조건문에 때려넣었습니다.

 

조건

- 대소문자 구분하지 않는다. (r과 R은 같다)

- 띄어쓰기 구분한다. ('rr r'은 회문이 아니다)

#include<iostream>
#include<string>
using namespace std;
int main(){

	string s; int i;
	getline(cin, s);

	int len = s.length();
	int halflen = len / 2;

	for (i = 0; i<halflen; i++){
		if ((((s.at(i) >= 'A') && (s.at(i) <= 'Z')) || ((s.at(i) >= 'a') && (s.at(i) <= 'z'))) && (((s.at(len - i - 1) >= 'A') && (s.at(len - i - 1) <= 'Z')) || ((s.at(len - i - 1) >= 'a') && (s.at(len - i - 1) <= 'z')))){ //char일 때
			if ((s.at(i) - s.at(len - i - 1)) == 32 || (s.at(len - i - 1) - s.at(i)) == 32 || (s.at(len - i - 1) == s.at(i))){

			}
			else{
				cout << "NOT Palindrome" << endl;
				break;
			}
		}
		else if (s.at(len - i - 1) != s.at(i)){
			cout << "NOT Palindrome" << endl;
			break;
		}
	}
	if (i == halflen){
		cout << "Palindrome" << endl;
	}


	return 0;
}

 

 

 

 

 

 

---

 

세 번째, 띄어쓰기를 무시하는 알고리즘입니다.

이 경우에는.. 반만 탐색할 수 없습니다.. 그래서 두 개의 기준을 세웠습니다.

그리고 이 두 화살표가,

       

똑같은 위치를 가리키거나(띄어쓰기 제외한 글자 수가 홀수일 때), 바로 옆에 있을 때(띄어쓰기 제외한 글자 수가 짝수일 때) 모든 글자를 확인한 것인데요, 더 간단하게 생각해보면 초록 화살표가 연두 화살표와 같거나, 더 왼쪽에 있을 때..! 다 확인하고도 남았다고 할 수 있겠군요.

이것도 그냥 조건 때려박아!!

 

조건

- 대소문자 구분하지 않는다. (r과 R은 같다)

- 띄어쓰기 구분하지 않는다. ('rr r'은 회문이다)

#include<iostream>
#include<string>
using namespace std;
int main(){

	string s; int i;
	getline(cin, s);

	int len = s.length();
	int halflen = len / 2;

	int left = 0; int right = len - 1;

	while(true){
		
		while (s.at(left) == ' ') left++;
		while (s.at(right) == ' ') right--;


		if (right>=left) break;


		if ((((s.at(left) >= 'A') && (s.at(left) <= 'Z')) || ((s.at(left) >= 'a') && (s.at(left) <= 'z'))) && (((s.at(right) >= 'A') && (s.at(right) <= 'Z')) || ((s.at(right) >= 'a') && (s.at(right) <= 'z')))){
			if ((s.at(left) - s.at(right)) == 32 || (s.at(right) - s.at(left)) == 32 || (s.at(right) == s.at(left))){

			}
			else{
				cout << "NOT Palindrome" << endl;
				return 0;
			}
		}
		else if (s.at(right) != s.at(left)){
			cout << "NOT Palindrome" << endl;
			return 0;
		}
	}

	cout << "Palindrome" << endl;

	return 0;
}

     

 

 

(이 코드를 짜고 나니 두 번째 내용을 더 깔끔하게 수정해서 이것도 고치고 싶었지만 귀찮아서.. ㅎㅎ..)

 

 

 

 

 

-

https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8