SW Expert Academy 의 1215번 문제입니다.
이 문제는 회문의 갯수를 찾는 문제입니다.
회문이란, 앞에서 읽으나, 뒤에서부터 읽으나 똑같은 문장이나 단어를 말합니다.
예를 들면, abba 나, level 등과 같은 문자열들을 말합니다.
8x8 글자판에서 가로 및 세로를 모두 파악하여, 정해진 길이를 가진 회문의 총 갯수를 구합니다.
위에서 초록색으로 칠해진 부분들이 회문들입니다.
단, 분홍색으로 칠해진 부분은 경로를 따라가면 회문이 맞지만, 직선이 아니므로 답이 아닙니다.
- 난이도 : 2
문제 조건
총 10개의 테스트 케이스가 주어진다.
글자판은 정사각형이며, 각 칸에 들어가는 글자는 char type의 ‘A’,’B’,’C’이다.
A, B, C 등도 길이가 1짜리인 회문으로 본다.
회문은 글자판 내에서 직선인 것들에서만 판단한다.
Input
첫 줄에는 찾아야 하는 회문의 길이, 다음 줄에는 테스트 케이스(글자판)이 주어진다.
Output
각 테스트 케이스에서 회문이 몇 개 있는지 갯수를 출력한다.
처음에 생각한 아이디어
어차피 8x8 글자판 내의 정해진 길이의 문자열들은 모두 살펴보아야 하므로,
가로줄 및 세로줄에서 문자 패턴을 모두 확인하도록 하였습니다.
맨 앞과 맨 뒤를 비교해 다르면 바로 넘어가고, 같으면 인덱스를 앞에서는 하나 증가, 뒤에서는 하나 감소시켜 반복 비교하였습니다.
소스코드 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main() {
int test_case;
int patternLen;
char string[8][8];
int i=0, j=0, count = 0, flag = 0;
int startPoint = 0;
int n = 8;
for (int T = 0; T < 10; T++) {
scanf("%d", &patternLen);
for (int i = 0; i < 8; i++)
scanf("%s",string[i]);
// 가로방향 살펴보기
for (int k = 0; k < 8; k++) {
// i=0부터 시작하여, i+(patternLen-1) 값이 k 이하일때 까지만 반복한다.
while (startPoint + (patternLen)-1 <= n-1) {
i = startPoint;
j = i + (patternLen)-1;
for (int m = 0; m < patternLen / 2; m++) {
if (string[k][i] == string[k][j]) {
i++; j--;
flag = 1;
}
else { // 같지 않으면 회문이 아니므로
flag = 0;
break;
}
}
if (flag == 1)
count++;
startPoint++;
}
startPoint = 0;
}
// 세로방향 살펴보기
for (int k = 0; k < 8; k++) {
// i=0부터 시작하여, i+(patternLen-1) 값이 k 이하일때 까지만 반복한다.
while (startPoint + (patternLen)-1 <= n - 1) {
i = startPoint;
j = i + (patternLen)-1;
for (int m = 0; m < patternLen / 2; m++) {
if (string[i][k] == string[j][k]) {
i++; j--;
flag = 1;
}
else { // 같지 않으면 회문이 아니므로
flag = 0;
break;
}
}
if (flag == 1)
count++;
startPoint++;
}
startPoint = 0;
}
printf("#%d %d\n", T+1, count);
count = 0;
}
}
소스코드 2 (C++의 vector를 사용)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <string.h>
#include <fstream>
#include <vector>
using namespace std;
int n = 8;
int find(vector< vector<char>> string, int patternLen) {
int startPoint = 0;
int i=0, j=0, flag=0;
int count = 0;
for (int k = 0; k < n; k++) {
// i=0부터 시작하여, i+(patternLen-1) 값이 k 이하일때 까지만 반복한다.
while (startPoint + (patternLen)-1 <= n - 1) {
i = startPoint;
j = i + (patternLen)-1;
for (int m = 0; m < patternLen / 2; m++) {
if (string[k][i] == string[k][j]) {
i++; j--;
flag = 1;
}
else { // 같지 않으면 회문이 아니므로
flag = 0;
break;
}
}
if (flag == 1)
count++;
startPoint++;
}
startPoint = 0;
}
for (int k = 0; k < n; k++) {
// i=0부터 시작하여, i+(patternLen-1) 값이 k 이하일때 까지만 반복한다.
while (startPoint + (patternLen)-1 <= n - 1) {
i = startPoint;
j = i + (patternLen)-1;
for (int m = 0; m < patternLen / 2; m++) {
if (string[i][k] == string[j][k]) {
i++; j--;
flag = 1;
}
else { // 같지 않으면 회문이 아니므로
flag = 0;
break;
}
}
if (flag == 1)
count++;
startPoint++;
}
startPoint = 0;
}
return count;
}
int main() {
int test_case, patternLen;
char ch;
int startPoint = 0;
int i = 0, j = 0, flag = 0, count = 0;
vector < vector<char> > string;
for (int T = 0; T < 10; T++) {
cin >> patternLen;
for (int row = 0; row < 8; row++) {
vector<char> element;
for (int col = 0; col < 8; col++) {
cin >> ch;
element.push_back(ch);
}
string.push_back(element);
}
count = find(string, patternLen);
cout << "#" << T+1 << " " << count <<endl;
string.clear();
}
}
알고리즘은 동일하지만 C++의 vector 함수를 사용해 보는 연습을 위해 작성한 것입니다.
cin, cout 등을 사용하므로 소스코드 1번보다는 2번의 실행시간이 더 느립니다.