1254. 팰린드롬 만들기

같은 문자를 체크하며, 팰린드롬을 확인하는 로직

같은 문자를 체크할 경우

사진과 같이 V라인을 확인할 수 있습니다.

대신 2가지의 V라인이 존재하므로,

이를 구분하여 로직을 구현했습니다.

0, 0부터 대각선으로 내려가며, 꼭지점 or 변곡점을 확인할 경우,

대각선(/) 방향으로 올라가며 체크합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1254 { static boolean[][] dp = new boolean[1001][1001]; static String inputStr; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); inputStr = st.nextToken(); for (int y = 0; y < inputStr.length(); y++) { for (int x = y; x < inputStr.length(); x++) { if (inputStr.charAt(y) == inputStr.charAt(x)) { dp[y][x] = true; } } } int startPoint = inputStr.length()/2; if (inputStr.length()%2 == 0) { startPoint--; } int result = -1; for (int i = startPoint; i+1 <= inputStr.length()-1; i++) { if (i-1 >= 0 && dp[i-1][i+1]) { int temp = searchChar(i-1, i+1); if (temp != -1) { result = temp; } } if (i >= 0  && dp[i][i+1]) { int temp = searchChar(i, i+1); if (temp != -1 && (result == -1 || result > temp)) { result = temp; } } if (result != -1) { System.out.println(result); return; } } System.out.println(inputStr.length()*2-1); } static public int searchChar(int y, int x) { while (y >= 0 && x < inputStr.length()) { if (!dp[y][x]) { return -1; } y--; x++; } y++; x--; if (x < inputStr.length()-1) { return -1; } int totalNum = inputStr.length()+y; return totalNum; } }