[SWEA] 1216. 회문2

문제

1216. [S/W 문제해결 기본] 3일차 - 회문2
'기러기', 'level'과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문이라고 함. 주어진 글자판에서 가장 긴 회문의 길이를 구하라.

풀이

회문1과 유사한 문제로 기본적인 풀이법은 일치한다. (난 회문2부터 풀었지만..)

단, 가장 긴 회문의 길이를 구하는 게 목적이므로 getMaxLength~() 함수에서 while문을 이용하여 글자판의 끝까지 확인해야한다.

자바코드

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

class Solution
{
	static char [][] arr = new char[100][100];
	
	public static void main(String args[]) throws Exception
	{
		System.setIn(new FileInputStream("res/input (5).txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			// input
			int t=sc.nextInt();
			String s = "";
			
			for (int i=0; i<100; i++) {
				s = sc.next();
				for (int j=0; j<100; j++) {
					arr[i][j] = s.charAt(j);
				}
			}
			
			int maxLength = -1;
			int m;
			for (int i=0; i<100; i++) {
				for (int j=0; j<100; j++) {
					m = getMaxLengthHorizontal(i, j, j);
					if (m > maxLength) maxLength = m;
					m = getMaxLengthHorizontal(i, j, j+1);
					if (m > maxLength) maxLength = m;
					m = getMaxLengthVertical(i, i, j);
					if (m > maxLength) maxLength = m;
					m = getMaxLengthVertical(i, i+1, j);
					if (m > maxLength) maxLength = m;
				}
			}
			
			
			System.out.printf("#%d %d\n", test_case, maxLength);
		}
	}
	public static int getMaxLengthHorizontal(int r, int c1, int c2) {
		// c1==c2 ? 홀수 : 짝수개
		if (c2<100 && arr[r][c1] != arr[r][c2]) return 0;
		
		while(c2<99 && c1>0) {
			c2 += 1; c1 -= 1; 
			if (arr[r][c1] != arr[r][c2]) return c2-c1-1;
		}
		
		return c2-c1+1;
	}
	
	public static int getMaxLengthVertical(int r1, int r2, int c) {
		// c1==c2 ? 홀수 : 짝수개
		if (r2<100 && arr[r1][c] != arr[r2][c]) return 0;
		
		while(r2<99 && r1>0) {
			r2 += 1; r1 -= 1; 
			if (arr[r1][c] != arr[r2][c]) return r2-r1-1;
		}
		
		return r2-r1+1;
	}
}

헷갈린 부분

1) 최종코드
public static int getMaxLengthHorizontal(int r, int c1, int c2) {
	// c1==c2 ? 홀수 : 짝수개
	if (c2<100 && arr[r][c1] != arr[r][c2]) return 0;

	while(c2<99 && c1>0) { // c1,c2가 arr(글자판)영역 밖으로 넘어가지 않게 하기 위한 조건
		c2 += 1; c1 -= 1; 
		if (arr[r][c1] != arr[r][c2]) return c2-c1-1;
	}

	return c2-c1+1;
}

위 함수는 회문의 길이를 반환한다. 그런데 return c2-c1-1; 부분을 처음에 생각을 못했다.

2) 초기코드
if (arr[r][c1-1] != arr[r][c2+1]) return c2-c1+1;
c2 += 1; c1 -= 1;

2) 했으면 깔끔하지만, 왠지 깔끔하지 않고 같은 연산을 두 번 해서 1)로 했다. 그런데 c2-c1+1 부분을 바꾸지 않아서 정답에서 2씩 크게 나왔다! 다시 보니 양 끝 문자가 일치하지 않을 때(더 이상 회문이 아니게 되었을 때) 리턴하므로 늘렸던 길이를 다시 줄여야 했다. 그 결과 c2-c1-1 이 되었다. while문 아래는 회문이지만 글자판 영역을 벗어나서 더 이상 갈 곳이 없어서 반환하는 것이므로 길이를 줄여줄 필요가 없다.

다시 보니 2)가 직관적이여서 훨씬 나은 것 같다 ㅎㅎ...

아쉬운 부분

1. 가로, 세로 코드가 중복된다는 것. (나중엔 전치행렬로!)
2. main 함수의 이중 for문.. 저게 최선이었을까?