[인프런 자바 알고리즘 문제풀이] 7. 희문 문자열

설명

앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 희문 문자열이라고 합니다.

문자열이 입력되면 해당 문자열이 회문 문자열이면 "YES", 회문 문자열이 아니면 "NO"를 출력하는 프로그램을 작성하세요. 단 회문을 검사할 때 대소문자를 구분하지 않습니다.

입력

첫 줄에 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다.

출력

첫 번째 줄에 회문 문자열인지의 결과를 YES 또는 NO로 출력합니다.

입력 예시

gooG

출력 예시

YES

---

My Answer 1 - 오답

짝수개의 문자열만 허용되는줄 알았는데 sskss 처럼 홀수도 가능한 것이였다....

import java.util.Locale;
import java.util.Scanner;

public class Main {
    public String solution(String str) {
        StringBuilder answer = new StringBuilder();
        String upperStr = str.toUpperCase(Locale.ROOT);
        int halfLength = (upperStr.length()) / 2;
        //문자열의 길이가 짝수 인 경우
        if((upperStr.length()) % 2 == 0) {
            String beforeHalfStr = upperStr.substring(0, halfLength);
            String afterHalfStr = upperStr.substring(halfLength);
            StringBuilder reverseHalfStr = new StringBuilder(afterHalfStr).reverse();
            if(beforeHalfStr.equals(reverseHalfStr.toString())) {
                answer.append("YES");
            }
        } else {
            answer.append("NO");
        }
        return answer.toString();
    }
    public static void main(String[] args) {
        Main C = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        System.out.println(C.solution(str));
    }
}

My Answer 2 - 정답

import java.util.Locale;
import java.util.Scanner;

public class Main {
    public String solution(String str) {
        StringBuilder answer = new StringBuilder();
        String upperStr = str.toUpperCase(Locale.ROOT);
        StringBuilder reverseStr = new StringBuilder(upperStr).reverse();
        if(upperStr.equals(reverseStr.toString())) {
            answer.append("YES");
        } else {
            answer.append("NO");
        }


        return answer.toString();
    }

    public static void main(String[] args) {
        Main C = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        System.out.println(C.solution(str));
    }
}

시간 복잡도

for문이 없으니 O(1)

---

Lecture Answer

import java.util.Locale;
import java.util.Scanner;

public class Main {
    public String solution(String str) {
        String answer = "YES";
        String upperStr = str.toUpperCase(Locale.ROOT);
        int len = upperStr.length();
        for(int i = 0; i < len/2; i++) {
            if(upperStr.charAt(i) != upperStr.charAt(len - i - 1)) {
                return "NO";
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main C = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        System.out.println(C.solution(str));
    }
}

시간 복잡도

len/2만큼 반복해서 O(n)

---

궁금한게 O(1)이 상대적으로 더 빠른거 아닌가?ㅠㅠ왜 속도는 더 느릴까