문제 링크

접근 방법

• 문제 이해
  • 입력 첫번째 줄은 입력의 개수를 의미한다. (최대 30개까지 가능)
  • 입력값은 영문 알파벳 소문자로만 이루어져 있다. (최소 3자리 부터 100,000 자리 까지 가능)
  • ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 회문임으로 0 반환
  • ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문임으로 1 반환
  • 그 외는 2 반환
• 풀이 전략
  • 걍 하나씩 문자 빼고 회문인지 하나하나 확인 하면 되지 않나? → 완전 탐색
    • 시간 초과 이유는 시간복잡도에 따라 연산 횟수가 3천억번 될 수 있음.
  • 문제 다시 확인해보니 문제 분류가 투 포인트임
    • 문제 잘 좀 보자

시간초과 1번 풀이 : 완전탐색 전략

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        System.out.println("입력:");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; ++i) {
            String s = br.readLine();
            int result = solution(s);

            bw.write(result + System.lineSeparator());
        }

        br.close();
        bw.close();
    }

    private static int solution(String s) {
        // 회문
        if(isPalindrome(s)) {
            return 0;
        }
        // 유사 회문
        else if (isSimilarPalindrome(s)){
            return 1;
        }
        // 그 외
        else {
            return 2;
        }
    }

    public static boolean isPalindrome(String s) {
        return s.contentEquals(new StringBuilder(s).reverse());
    }

    public static boolean isSimilarPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            StringBuilder sb = new StringBuilder(s);
            sb.deleteCharAt(i);
            if (isPalindrome(sb.toString())) {
                return true;
            }
        }
        return false;
    }
}

통과 2번 풀이 : 투 포인터

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        System.out.println("입력:");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; ++i) {
            String s = br.readLine();
            int result = solution(s);

            bw.write(result + System.lineSeparator());
        }

        br.close();
        bw.close();
    }

    private static int solution(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // 만약 두 문자가 다르다면
                // 왼쪽 문자를 제거했을 때 회문이 되는지 확인
                if (isPalindrome(s, left + 1, right)) {
                    return 1; // 유사 회문
                }
                // 오른쪽 문자를 제거했을 때 회문이 되는지 확인
                if (isPalindrome(s, left, right - 1)) {
                    return 1; // 유사 회문
                }
                // 둘 다 아니면 일반 문자열
                return 2;
            }
            left++;
            right--;
        }
        // 회문인 경우
        return 0;
    }

    public static boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

유사회문 디버그표

주어진 문자열: summuus
left   right   s.charAt(left)   s.charAt(right)   작업 내용
------------------------------------------------------------
  0      6           s                   s          s와 s 비교 -> 같음
  1      5           u                   u          u와 u 비교 -> 같음
  2      4           m                   u          m와 u 비교 -> 다름

왼쪽 문자 제거
left   right   s.charAt(left)   s.charAt(right)   작업 내용
------------------------------------------------------------
  3      4           m                   u          m와 u 비교 -> 다름

오른쪽 문자 제거
left   right   s.charAt(left)   s.charAt(right)   작업 내용
------------------------------------------------------------
  2      3           m                   m          m와 m 비교 -> 같음

따라서 유사 회문

풀이 시간 복잡도 비교

• 1번은 O(T * n^2)의 시간복잡도를 가지는 알고리즘으로 최대 30 * (100,000 * 100,000) 으로 300,000,000,000 연산이 수행될 수 있음.
• 2번은 O(T * n)의 시간복잡도를 가지는 알고리즘으로 입력 값의 길이가 30 * 100,000으로 300만 연산이 수행될 수 있음.