PALINDROMIZE 시간 초과에 대해 질문드려요~

  • ison5059
    ison5059

    안녕하세요 자바로 PALINDROMIZE를 짜봤는데 시간초과가 뜨네요...
    어디서 시간을 많이 잡아 먹나 긴 문자열을 넣어봤는데
    입력 받은 문자열이 펠린드롬인지 검사하는 부분에서 시간이
    꽤 걸리는 거 같네요.. 아래는 제가 구현한 비교하는 방식인데
    이 방식 말고 더 좋은 방식이 있을까요?

    public static boolean checkPalin(String input){
    boolean check = true;
    int end = input.length() -1 ;

    for(int begin = 0; begin <= end; begin++){
            if(input.charAt(begin) != input.charAt(end)){
                check = false;
                break;
            }
            end--;
        }
        return check;
    }

    아니면 자바론 답이 없으니 다른 언어로 작성을 해야할까요..?
    정답 통계를 보니 자바로는 3분만 통과를 하셨더군요 ㄷㄷ;


    5년 전
2개의 댓글이 있습니다.
  • ison5059
    ison5059

    다른 분들 글을 읽어보니 이 부분 문제보다 입력 부분에서 문제가 되는거 같네요.. BufferedReader 가 좀 더 빠르다고 해서 했는데도 시간초과가 나네요...;


    5년 전 link
  • WeissBlume
    WeissBlume

    이 문제를 어떻게 접근하신지 몰라 섣불리 말씀드리긴 어려우나, Java로도 특정 알고리즘과 BufferedReader를 활용하면 (간신히?) 통과 가능한 것 같습니다.


    KMP (Knuth Morris Pratt)알고리즘을 알아보세요.


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.