백준 - 회문 (17609) : JAVA

문제 유형
투 포인터

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다.
2. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다.
3. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 
4. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

직관적으로 봤을 때 양 끝에서 포인터를 이동하며 회문 or 유사회문인지를 판단하면됩니다.

 static int pointer(int left, int right, String word, int flag) {

     while (left <= right) {

         if (flag >= 2) break;

         char lc = word.charAt(left);
         char rc = word.charAt(right);

         if (lc == rc) {

             left++;
             right--;
         } else {
             if (word.charAt(left + 1) == word.charAt(right) && word.charAt(left) == word.charAt(right - 1)) {
                 int a = pointer(left + 1, right, word, flag + 1);
                 int b = pointer(left, right - 1, word, flag + 1);


                 return Math.min(a, b);
             } else if (word.charAt(left + 1) == word.charAt(right)) {
                 flag++;
                 left++;
             } else if (word.charAt(left) == word.charAt(right - 1)) {
                 flag++;
                 right--;
             } else {
                 flag = 2;
             }
         }

     }

     return flag;
 }

포인터를 이동하다가 left, right가 가르키는 값이 다르다면 문자열을 삭제해야합니다.

여기서 주의해야할점은 가능한 삭제의 경우가 2개인 경우입니다.

예를 들어서 abbab라는 문자열이 존재한다고 가정합시다.

left = 0, right = 5 일 때 a를 삭제할 수도 있고 b를 삭제할 수도 있습니다.
a를 삭제하면 유사회문이 될수 없고 b를 삭제하면 유사회문이 될 수 있습니다.
이러한 경우는 재귀를 통해 분기처리를 해줘서 반환되는 flag값이 더 작은 것을 선택합니다.
pointer가 반환하는 정수 값은 0,1,2 중에 하나이기 때문에 재귀 호출은 flag가 2일때까지로 제한됩니다.

시간 복잡도
O(N)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();

        for (int t=1; t<=T; t++) {

            String word = br.readLine();
            
            int flag = 0;
            int left = 0;
            int right = word.length()-1;
            
            flag = pointer(left, right, word, flag);
            
            sb.append(flag).append("\n");

        }

        System.out.println(sb.toString());

    }
    
    static int pointer(int left, int right, String word, int flag) {
    	
    	while (left <= right) {
        	
        	if (flag >= 2) break;
        	
        	char lc = word.charAt(left);
        	char rc = word.charAt(right);
        	
        	if (lc == rc) {
        		
        		left++;
        		right--;
        	}
        	else {
        		if (word.charAt(left+1) == word.charAt(right) && word.charAt(left) == word.charAt(right-1)) {
        			int a = pointer(left+1, right, word, flag+1);
        			int b = pointer(left, right-1, word, flag+1);
        		
        			
        			return Math.min(a, b);
        		}
        		else if (word.charAt(left+1) == word.charAt(right)) {
        			flag++;
        			left++;
        		}
        		else if (word.charAt(left) == word.charAt(right-1)) {
        			flag++;
        			right--;
        		}
        		else {
        			flag = 2;
        		}
        	}
        	
        }
    	
    	return flag;
    }

}