[SWEA] #1216 - 회문2

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14Rq5aABUCFAYi 

SW Expert Academy

 

💡 문제

---

[설명]

"기러기" 또는 "level"과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(palindrome)이라 한다.

주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.

위와 같은 글자 판이 주어졌을 때, 길이가 가장 긴 회문은 붉은색 테두리로 표시된 7칸짜리 회문이다.

 

[제약 사항]

1. 각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다.

2. 글자 판은 무조건 정사각형으로 주어진다.

 

💡 아이디어

---

#1215 회문1 문제에서 응용된 문제이다. '#1215 - 회문'에 대한 풀이는 아래에서 확인할 수 있다. 

https://coderand.tistory.com/entry/SWEA-1215-%ED%9A%8C%EB%AC%B81

[SWEA] #1215 - 회문1

이 문제는 회문1 코드를 조금 수정해서 풀었다.

이 문제에선 배열의 크기가 100X100이기 때문에 최대 회문의 길이는 100이 된다.

그러므로 길이를 나타내는 변수를 만들어 100, 99, 98 ··· 1의 길이를 가지는 회문을 탐색하다가 회문이 존재하면 무한루프를 탈출하도록 했다.

 

💡 소스코드

---

import java.io.FileInputStream;
import java.util.Scanner;

public class P_1216 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);

		for (int TC = 1; TC <= 10; TC++) {
			int T = sc.nextInt();

			int[][] array = new int[100][100];
			int length = 100;
			boolean flag = true;

			for (int i = 0; i < 100; i++) {
				String s = sc.next();
				for (int j = 0; j < 100; j++)
					array[i][j] = s.charAt(j);
			}

			while (flag) {
				// 가로 탐색
				for (int i = 0; i < 100; i++) {
					for (int j = 0; j < 100 - length + 1; j++) {// T만큼 탐색할 수 있는 만큼만 증가
						int check = 0;
						for (int k = 0; k < length / 2; k++) {
							if (array[i][j + k] != array[i][j + length - k - 1])// 대응하는 값이 다르면
								check++;// 증가
						}
						if (check == 0)// 0 : 전부 같을 때 | !0 : 다른 게 있을 때
							flag = false;
					}
				}

				// 세로 탐색
				for (int i = 0; i < 100 - length + 1; i++) {// T만큼 탐색할 수 있는 만큼만 증가
					for (int j = 0; j < 100; j++) {
						int check = 0;
						for (int k = 0; k < length / 2; k++) {
							if (array[i + k][j] != array[i + length - k - 1][j])
								check++;
						}
						if (check == 0)
							flag = false;
					}
				}
				
				length--;
			}

			System.out.println("#" + TC + " " + (length + 1));
		}
	}
}

 

💡 결과

---

100X100의 배열을 탐색하기 때문에 꽤 시간이 많이 들었다.

회문의 길이가 50보다 크다면 회문의 길이를 100으로 잡고 탐색하는 것이 효율적이지만,

회문의 길이가 50보다 작다면 길이를 줄이면서 불필요한 탐색을 계속하기 때문에 시간이 많이 소요된다.

나중에 시간이 된다면 조금 더 효율적으로 코드를 작성해보면 좋을 것 같다.

그리고, 회문의 경우 익숙하게 등장하는 문제인 만큼 다양한 회문 문제를 풀어보는 것이 좋겠다.