[SWEA] 1216 : 회문 2

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AV6kld8aisgDFASb&contestProbId=AV14Rq5aABUCFAYi&probBoxId=AV-4MojKLNADFATz&type=PROBLEM&problemBoxTitle=%5BD2~D3+%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4%5D+%EA%B8%B0%EC%B4%88+%EB%8B%A4%EC%A7%80%EA%B8%B0+Part4&problemBoxCnt=14 

SW Expert Academy

처음에 덱을 이용해서 풀려고 했는데 덱의 동기화 특성 때문인지( 더 알아봐야 함 ) 제대로 활용할 수 없었음.

>> 깊은복사와 얕은복사 개념. new로 새로 정의를 해줘야 다른 객체로 선언할 수 있음. 같은 주소값을 바라보게 했기 때문에 같은 기존의 덱에 영향을 끼친 거였다.

 

결국 그냥 완전탐색으로 풀었다.

시작점과 같은 값이 나올 때마다 회문인지 판별해주는 메서드를 호출해줌.

 

내 코드

메모리 : 26184 KB

시간 : 201 ms

코드길이 : 2068 B

 

[내 코드]

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

public class Solution {
	static char[][] graph = new char[100][100];
	static int result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		for(int t = 1; t <= 10; t++) {
			int testcase = Integer.parseInt(br.readLine());
			sb.append('#').append(testcase).append(' ');
			//가장 짧은 회문의 길이 1
			result = 1;
			//그래프 입력
			for(int i = 0; i < 100; i++) {
				String row = br.readLine();
				for(int j = 0; j < 100; j++) {
					graph[i][j] = row.charAt(j);
				}
			}
			//회문찾기
			for(int row = 0; row < 100; row++) {
				for(int column = 0; column < 100; column++) {
					getLength_hori(row, column);
					getLength_verti(row, column);
				}
			}
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	
	//1. 가로로 가장 긴 회문 찾기
	public static void getLength_hori(int row, int column) {
		for(int c = column + 1; c < 100; c++) {
			if(graph[row][column] == graph[row][c]) {
				int time = (c - column + 1) / 2;
				if(isPalindrome_hori(row, column, c, time))
					result = Math.max(result, c - column + 1);
			}
		}
	}
	//2. 세로로 가장 긴 회문 찾기
	public static void getLength_verti(int row, int column) {
		for(int r = row + 1; r < 100; r++) {
			if(graph[row][column] == graph[r][column]) {
				int time = (r - row + 1) / 2;
				if(isPalindrome_verti(row, column, r, time))
					result = Math.max(result, r - row + 1);
			}
		}
	}
	
	public static boolean isPalindrome_hori(int row, int column, int c, int time) {
		for(int i = 0; i < time; i++) {
			if(graph[row][column + i] != graph[row][c - i])
				return false;
		}
		return true;
	}

	public static boolean isPalindrome_verti(int row, int column, int r, int time) {
		for(int i = 0; i < time; i++) {
			if(graph[row + i][column] != graph[r - i][column])
				return false;
		}
		return true;
	}
}