Palindrome(회문) 알고리즘

Palindrome이라는 단어가 뭔지 몰랐는데 문제를 읽고 문자열이 데칼코마니를 만들어내면 풀 수 있다고 생각함.

 

Sample Input

madam → O

maddam → O

pppaapp → X

sziofsjifzsfwu8 -> X

 

Palindrome란?

팰린드롬이란 우리 말로 ‘회문(回文)’으로 번역되며 ‘eye' 'madam'처럼 역순으로 읽어도 같은 말이나 구절 또는 숫자를 말하며, 일반적으로 단어 사이 구두점과 뛰어 쓰기 조정은 허용된다.

 

이 문제를 접근할땐 시간복잡도로 O(N)의 복잡도를 가질필요가 없다고 생각함.

O(N/2)의 복잡도를 가지면서 left는 인덱스를 그대로 증가하면서 right은 배열의 길이에 증가된 인덱스만큼 감소시키면 적절하게 풀 수 있을거라 생각함.

 

 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // madam
        String A = sc.next();
        int count = 0;
        for (int i = 0; i < A.length() / 2; i++) {
            if (A.charAt(i) == A.charAt(A.length() - i - 1)) count++;
        }
        System.out.println(count == A.length() / 2 ? "Yes" : "No");
    }

 

최종적으로 left와 right가 같으면 카운트를 센 다음 이 카운트가 N.length/2와 동일하면 일치하는지 판별가능하다.