[백준] 회문

시간복잡도 생각해보기

• 최대 길이가 2500이라서 O(N^2)도 가능한 문제였다.
• 투 포인터를 이용해 풀었으므로 문자열 길이 n에 대해서 다 돌면: O(N)
• 하지만 문자열이 다른 경우에 그 문자열을 제외하고 돌아야 하므로 O(N)
• 따라서 총 O(N^2) 에 수렴함

풀이 아이디어

• 투 포인터를 이용해서 회문인지 검사하고, 만약 해당 r과 l에 해당하는 문자 char이 다르면, r과 l을 제외한 문자열을 제외하고는 각각 회문인지 다시 검사한다.

의사코드 / 풀이 과정

전체적인 틀: 투 포인터 활용

while(l<r){
만약 str.charAt(l) != str.charAt(r): //이면 회문이 아니므로
    return false;
else:
    l++; //계속 탐색한다.
    r--; 
}

• 만약 str.charAt(l) != str.charAt(r): 이면, 그 l,r을 각각 전체 str에서 제거하고 회문이 되는지를 확인한다.

  boolean skipLeft = isPalindrome(skipLeftStr,0, skipLeftStr.length()-1);
  boolean skipRight = isPalindrome(skipRightStr,0, skipLeftStr.length()-1);
  if(skipLeft || skipRight) {
    flag = 1;
    return true;
  }else {
    flag = 2;
    return false;
  }

• 만약 회문이 된다면: flag:1
• 만약 회문이 안된다면: flag:2
• 원래 회문이었다면: flag:0

전체 코드

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

public class 회문 {
    static int flag;
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N;i++) {
            flag = 0;
            String str= br.readLine();
            boolean isPalin = check(str);
            if(!isPalin && flag == 2) {
                sb.append(flag).append("\n");
            }else if(isPalin && flag ==1) {
                sb.append(flag).append("\n");
            }else if(isPalin && flag ==0) {
                sb.append(flag).append("\n");
            }
        }
        System.out.println(sb);
    }
    private static boolean check(String str) {
        int l = 0;
        int r = str.length() - 1;
        while(l<r) {
            if(str.charAt(l) != str.charAt(r)) {
                String skipLeftStr = getString(str,l);
                String skipRightStr = getString(str,r);
                boolean skipLeft = isPalindrome(skipLeftStr,0, skipLeftStr.length()-1);
                boolean skipRight = isPalindrome(skipRightStr,0, skipLeftStr.length()-1);
                if(skipLeft || skipRight) {
                    flag = 1;
                    return true;
                }else {
                    flag = 2;
                    return false;
                }
            }
            l ++ ;
            r -- ;
        }
        return true;    
    }
    private static boolean isPalindrome(String str, int l, int r) {
        while(l<r) {
            if(str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    private static String getString(String str,int index) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<str.length();i++) {
            if(i == index) {
                continue;
            }
            sb.append(str.charAt(i));
        }
        return sb.toString();    
    }
}