[HackerRank] Palindrome Index(투포인터) 📌

 

 

문제 

 

거꾸로 읽어도 똑같은 문자열이 되도록 하기 위해 몇번째 문자를 제거해야 하는지 구하기 

이미 palindrome 이거나 답이 없으면 -1 반환

이게 투포인터구나.. 

 

 

 

 

내 풀이 

 

일단 틀렸다. test case 몇 개 통과가 안되고, 시간이 초과되어서 점수 한 18점 정도 받았음 .. ㅠ

앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은지를 어케 알 수 있을까 하다가 더 고민하지 않고 

문자열의 첫번째부터 삭제해가면서

reverse()를 사용했는데 그럼 다시 또 reverse를 해야하고, 

deleteCharAt()으로 삭제하고 나서 다시 원래 문자열을 담아야 하고 그래서 복잡하긴 했다 .... ㅠ

 

private static int palindromeIndex(String s) {

    StringBuffer sb = new StringBuffer();
    sb.append(s);

    // 이미 맞으면 -> return -1
    if(sb.toString().equals(sb.reverse().toString())) {
        return -1;
    }
    sb.reverse();

    // 문자열에서 앞에서부터 하나씩 지우면서 뒤집어도 같은 문자열인지 확인
    for(int i=0; i < s.length(); i++) {
        sb.deleteCharAt(i);
        if(sb.toString().equals(sb.reverse().toString())) {
            return i;
        }
        sb.reverse().replace(0, sb.length(), s);
    }

    return -1;

}

 

 

 

아 이 코드는 이해할 만 하다 헀는데 

이것도 타임 초과 ㅡㅡ 

 

private static int palindromeIndex(String s) {

    // 이미 회문이면 -1 반환
    if(isPalindrome(s)) {
        return -1;
    }

    // 하나씩 삭제하면서 확인 (그 문자를 제외한 문자의 합)
    for(int i=0; i<s.length(); i++) {
        // (처음 ~ i-1번째 문자) + (i+1번째 ~ 끝 문자) -> i번째를 제외한 문자열의 합
        String str = s.substring(0, i) + s.substring(i + 1);
        if(isPalindrome(str))
            return i;
    }

    // 해당하는게 없으면 -1 반환
    return -1;
}

// 회문인지 확인하는 메소드
private static boolean isPalindrome(String s) {

    // 양쪽 끝 설정
    int start = 0;
    int end = s.length() - 1;

    // 둘이 만날 때까지
    while(start < end) {
        // start번째의 문자와 end번째의 문자가 다르면 false (회문 아님)
        if(s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start ++;
        end --;
    }
    // 만날 때까지 다른 문자가 없었으면 true (회문)
    return true;
}

 

 

 

다른 사람 풀이 

 

private static int palindromeIndex(String s) {
 
    int start = 0; 
    int end = s.length() - 1; 

    // 양쪽 끝에서부터 만날 때까지 회문인지 확인
    while (start < end) {
        if(s.charAt(start) != s.charAt(end)) 
            break;
        start ++;
        end --; 
    }
    // 만날 때까지 다른 문자 없으면 회문 -> -1 반환
    if(start >= end) 
        return -1;

    // 문자열이 회문이 아닐 때 
    // 반환할 인덱스 구하기
    int i = start; 
    int j = end;

    // 전체 string이 회문 아닌건 알았으니까 첫번째 문자 제외
    start ++;

    // 회문인지 확인
    while(start < end) {
        if(s.charAt(start) != s.charAt(end))
            return j;
        start ++; 
        end --;
    }

    // 회문이면 현재 제외한 i번째 인덱스 반환
    return i;

}

 

솔직히 두번째 while문에서 왜 문자열의 끝에서부터 제외하는지 이해가 안된다

 

앞에서부터 제외하면, 

한 글자를 제외하고 다시 비교를 수행할 때 매번 문자열의 모든 길이를 재계산해야 함

 

뒤에서부터 제외하면, 

문자열의 길이가 변하지 않기 때문에 불필요한 계산을 줄일 수 있음 -> 문자열의 길이가 길 수록 효율적

 

뭔말이지? ㅠ