[Algo] 백준 23304 아카라카 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/23304

메모리 : 57976KB

시간 : 280ms

언어 : Java 11

---

코드

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

public class Main {
	static String str;
	static boolean flag;

	public static <T> void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();
		flag = true;
		int len = str.length();
		pal(0, len - 1);
		for (int i = len / 2; i > 0 && flag; i /= 2) {
			pal(0, i - 1);
		}
		if (flag) {
			System.out.println("AKARAKA");
		} else {
			System.out.println("IPSELENTI");
		}
	}

	private static void pal(int left, int right) {
		if (left >= right) {
			flag = true;
			return;
		}
		if (str.charAt(left) == str.charAt(right)) {
			pal(left + 1, right - 1);
		} else {
			flag = false;
		}
	}
}

풀이

팰린드롬인가 검사하는 문제! 그런데 접두사와 접미사가 또 팰린드롬이어야한다. 문자열 S가 아카라카 팰린드롬인가? 는 S의 접두사와 접미사를 다시 검사해야하는데, 다시 검사하는 경우 "S의 접두사" 가 다시 S가 되기 떄문에 "S의 접두사의 접두사" 가 또 팰린드롬이어야 한다.

이런 구조를 가졌기 때문에 재귀로 문제를 해결해야한다. flag 는 팰린드롬인가 검사하는 변수이다. for문에서 flag가 false인지를 검사하고있기 때문에, 팰린드롬이 아닌 경우 바로 for문이 종료되고 정답을 출력할 수 있다.