회문(palindrome)에 대해 알아보자

  • 21/9/2021
  • 읽는 시간 2분

회문

회문 SWEA 회문2 SWEA
회문이란 앞으로 읽어도 뒤로 읽어도 같은 단어이다. 회문1 같은 경우에는 8x8 단어판와 길이가 주어지면 그 단어판에서 길이만큼의 회문 갯수를 세면 된다.

회문1

1string temp;
2for (int i=n; i<n+len; i++) {
3	temp += v[i][m];
4}
5string temp2 = temp;
6reverse(temp.begin(),temp.end());
7if(temp == temp2)
8	ans++;

와 같이 뒤집은 문자와 문자가 같으면 회문으로 처리했다.

회문2

회문2의 경우에는 회문1에서 단어판을 100x100으로 키우고 최대의 길이의 회문을 찾으면 된다.

 1int x(int len, int pos_y, int pos_x) {
 2	for (int i=0; i<len/2; i++) {
 3		if(v[pos_y][pos_x + i] != v[pos_y][pos_x + len - 1 - i])
 4			return 0;
 5	}
 6	return len;
 7}
 8int y(int len, int pos_y, int pos_x) {
 9	for (int i=0; i<len/2; i++) {
10		if(v[pos_y + i][pos_x] != v[pos_y + len - 1 - i][pos_x])
11			return 0;
12	}
13	return len;
14}
15
16for (int k=1; k<100; k++) {
17	for (int i=0; i<=100-k; i++) {
18		for (int j=0; j<100; j++) {
19			temp = y(k,i,j);
20			len = max(len,temp);
21		}
22	}
23	for (int i=0; i<100; i++) {
24		for (int j=0; j<=100-k; j++) {
25			temp = x(k,i,j);
26			len = max(len,temp);
27		}
28	}
29}

k가 길이, i가 열, j가 행으로 잡고 길이가 k일때 (i,j)에서 시작하는 회문을 찾고 있으면 길이를 반환해서 len값과 비교해서 큰 값을 len에 넣는다.

algorithm palindrome

댓글