[SWEA] #1215 - 회문1

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

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

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

주어진 8x8 평면 글자판에서 가로, 세로를 모두 보아 제시된 길이를 가진 회문의 총개수를 구하는 문제이다.

위와 같은 글자판이 주어졌을 때, 길이가 5인 회문은 붉은색 테두리로 표시된 4개가 있으며 따라서 4를 반환하면 된다.

[제약 사항]

1. 글자판의 크기는 8X8이다.

2. 가로, 세로에 대해 직선으로만 판단한다.

 

💡 아이디어

---

우선 회문을 찾기 위해서는 각 자리에 대응되는 문자가 일치하는 지를 확인하면 된다.

회문의 길이가 T라고 했을 때 2 / T를 이용해 양 끝에서부터 대응되는 지점을 찾으면 된다.

짝수와 홀수를 각각 다르게 생각해야 되는 건 아닌지 헷갈릴 수 있는데, 2 / T를 했을 때 T가 홀수이면 정가운데 문자는

자연스럽게 제외가 되므로 홀수와 짝수를 따로 구분할 필요는 없다.

회문을 찾는 방법을 알았다면, 우선 행부터 모두 탐색하고, 열을 모두 탐색하면 해답을 구할 수 있다.

 

💡 소스코드

---

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

public class P_1215 {

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

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

			int cnt = 0;
			int[][] array = new int[10][10];

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

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

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

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

 

💡 결과

---