728x90
처음에는 각 행과 열에서 0과 99에서 시작해서, 두 값이 같으면 start와 end를 1씩 감소 시키고, 아닌 경우에는 start와 end 중 하나만 감소시키며 검사하려고 하였는데, 재귀로 구현하였더니 case가 너무 많고 예외처리가 잘 안되어서 무한 루프가 일어났다.
두 값이 같지 않을 경우 start를 1 증가시키거나, end를 1 증가시키면서 값을 찾아야 하는데, 그 과정에서 최대 길이인 회문을 찾는 과정을 보장하지 못하였다.
그래서 이중 for문에서 값을 하나하나 돌며, 해당 index값을 중앙값으로 하는 최대 회문의 길이를 찾고, 그 중 가장 긴 회문의 길이를 반환하였다.
이 과정에서 회문의 길이가 홀수, 짝수인 경우가 있는데, 홀수인 경우는 해당 index에서 일정값만큼 빼고 더해주며 회문을 검사하면 되지만, 짝수인 경우는 해당 index와 바로 옆 index-1(또는 index+1) 값을 비교하면서 더해주어야 한다.
이 경우를 따로 처리하였다.
for (int i = 0; i < 100; i++) {
for (int j = 1; j < 100; j++) {
int idx = 1;
int tmp;
if (arr[i][j] == arr[i][j - 1]) { // 짝수
tmp = 2;
while (j - 1 - idx >= 0 && j + idx < 100) {
if (arr[i][j - 1 - idx] == arr[i][j + idx]) { // j를 가운데로 하는 최대 string 길이 찾기
tmp += 2;
idx++;
} else {
break;
}
}
} else {
tmp = 1; // 홀수
while (j - idx >= 0 && j + idx < 100) {
if (arr[i][j - idx] == arr[i][j + idx]) { // j를 가운데로 하는 최대 string 길이 찾기
tmp += 2;
idx++;
} else {
break;
}
}
}
그리고 row와 col을 따로따로 검사하여 그 중 큰 값을 결과값으로 출력하였다.
전체 코드
package SWEA0812;
import java.util.Scanner;
public class SWEA_1216_회문2 {
static char[][] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = 10;
for (int t = 1; t <= T; t++) {
int N = sc.nextInt();
arr = new char[100][100];
for (int i = 0; i < 100; i++)
arr[i] = sc.next().toCharArray();
int length = 0;
// row
for (int i = 0; i < 100; i++) {
for (int j = 1; j < 100; j++) {
int idx = 1;
int tmp;
if (arr[i][j] == arr[i][j - 1]) { // 짝수
tmp = 2;
while (j - 1 - idx >= 0 && j + idx < 100) {
if (arr[i][j - 1 - idx] == arr[i][j + idx]) { // j를 가운데로 하는 최대 string 길이 찾기
tmp += 2;
idx++;
} else {
break;
}
}
} else {
tmp = 1; // 홀수
while (j - idx >= 0 && j + idx < 100) {
if (arr[i][j - idx] == arr[i][j + idx]) { // j를 가운데로 하는 최대 string 길이 찾기
tmp += 2;
idx++;
} else {
break;
}
}
}
if (length < tmp) // 최댓값 찾기
length = tmp;
}
}
// col
for (int i = 1; i < 100; i++) {
for (int j = 0; j < 100; j++) {
int tmp = 1;
int idx = 1;
if (arr[i][j] == arr[i - 1][j]) {
tmp = 2;
while (i - 1 - idx >= 0 && i + idx < 100) {
if (arr[i - 1 - idx][j] == arr[i + idx][j]) {
tmp += 2;
idx++;
} else {
break;
}
}
} else {
while (i - idx >= 0 && i + idx < 100) {
if (arr[i - idx][j] == arr[i + idx][j]) {
tmp += 2;
idx++;
} else {
break;
}
}
}
if (length < tmp)
length = tmp;
}
}
System.out.println("#" + N + " " + length);
}
}
}
728x90
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] 1231 - 중위 순회 (0) | 2022.08.23 |
---|---|
[SWEA] 1873 - 상호의 배틀 필드 (자바/Java) (0) | 2022.08.22 |
[SWEA] 1210 - Ladder (자바/Java) (0) | 2022.08.11 |
[SWEA] 5432 - 쇠막대기 자르기 (자바/Java) (0) | 2022.08.11 |
[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java) (0) | 2022.08.11 |