[SWEA 1215번, 1216 / JAVA] 회문 1, 회문 2

Question

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

SW Expert Academy

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

SW Expert Academy

---

💡 Solution

1. 가로로 가능한 회문 수와 세로로 가능한 회문 수를 각각 구합니다.

2. (가로에서 구할 때) 만약 길이(N)가 5라면, 한 행당 0번째 열부터 3번째 열까지만 탐색해도 됩니다. 즉, 한 행당 "8 - N + 1"만큼을 탐색 범위로 잡습니다.

3. N개의 칸에서 "N / 2"만큼 탐색합니다. (만약 ABCBA 가 있다면 0번째 문자와 3번째 문자, 1번째 문자와 2번째 문자만 비교하면 되기에 총 N / 2만큼만 탐색하면 됩니다.)

 

회문1 풀이를 기반으로 회문2 문제를 푸시면 됩니다. 회문1에서는 N이 주어졌다면 회문2에서는 N이 주어지지 않기 때문에, N이 될 수 있는 범위인 1에서 100 범위를 탐색하는 반복문 하나를 추가하였습니다. (효율적이지 않은 방법일 수 있지만 당장의 코딩테스트를 준비 중이기에 ..)

 

💻 Code

회문 1 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SWEA1215 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
	
		for (int tc = 1; tc <= 10; tc++) {
			int N = Integer.parseInt(br.readLine());
			
			char[][] arr = new char[8][8];
			int count = 0;
			boolean flag = true;
			
			for(int i = 0; i < 8; i++) {
				String str = br.readLine();
				for (int j = 0; j < 8; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			//가로
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8 - N + 1; j++) {
					flag = true;
					for (int k = 0; k < N / 2; k++) {
						if (arr[i][j + k] != arr[i][j - k + N - 1]) {
							flag = false;
						}
					}
					if (flag == true) {
						count++;
					}
				}
			}
			
			//세로
			for (int i = 0; i < 8 - N + 1; i++) {
				for (int j = 0; j < 8; j++) {
					flag = true;
					for (int k = 0; k < N / 2; k++) {
						if (arr[i + k][j] != arr[i - k + N - 1][j]) {
							flag = false;
						}
					}
					if (flag == true) {
						count++;
					}
				}
			}
			
			System.out.printf("#%d %d\n", tc, count);
		}

	}
	
}

 

회문 2 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SWEA1216 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int tc = 1; tc <= 10; tc++) {
			int T = Integer.parseInt(br.readLine());
			
			char[][] arr = new char[100][100];
			int maxValue = 0;
			boolean flag = true;
			
			for(int i = 0; i < 100; i++) {
				String str = br.readLine();
				for (int j = 0; j < 100; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			
			for (int n = 0; n < 100; n++) {
				//가로
				for (int i = 0; i < 100; i++) {
					for (int j = 0; j < 100 - n + 1; j++) {
						flag = true;
						for (int k = 0; k < n / 2; k++) {
							if (arr[i][j + k] != arr[i][j - k + n - 1]) {
								flag = false;
							}
						}
						if (flag == true) {
							maxValue = Math.max(maxValue, n);
						}
					}
				}
				//세로
				for (int i = 0; i < 100 - n + 1; i++) {
					for (int j = 0; j < 100; j++) {
						flag = true;
						for (int k = 0; k < n / 2; k++) {
							if (arr[i + k][j] != arr[i - k + n - 1][j]) {
								flag = false;
							}
						}
						if (flag == true) {
							maxValue = Math.max(maxValue, n);
						}
					}
				}
				
			}
			
			System.out.printf("#%d %d\n", tc, maxValue);
		}
	}

}