본문으로 바로가기
반응형

Description

양쪽 어디부터 읽어도 같은 대칭 문자열(Palindrome)이 될 수 있도록 만들기 위해 몇번째 문자를 제거해야하는지 찾아 반환하는 문제입니다.

Solution 1. Two Pointers

public static int palindromeIndex(String s) {
    // Write your code here
    int len = s.length();
    int start = 0;
    int end = len-1;

    while(start < end){
        if(s.charAt(start) != s.charAt(end)){
            break;
        }
        start++; end--;
    }
    if(start >= end) return -1;

    int i = start;
    int j = end;
    start++;
    while(start < end){
        if(s.charAt(start) != s.charAt(end)){
            return j;
        }
        start++; end--;
    }
    return i;
}

먼저 두개의 포인터를 이용해 양쪽 끝에서부터 값이 달라지는 위치를 찾습니다.

그리고 두 값중 어떤 값을 반환해야하는지 찾기위해 왼쪽값을 제거하고 해당 위치부터 Palindrome문자열이 되는지 검증하고 아니라면 해당값의 인덱스를 반환 아닐 경우 처음 찾았던 값중 오른쪽 값의 인덱스를 반환해 줍니다.

Reference

 

Palindrome Index | HackerRank

Determine which character(s) must be removed to make a string a palindrome.

www.hackerrank.com

 

반응형

댓글을 달아 주세요

  1. Favicon of https://kyj0701.tistory.com BlogIcon Vuntus 2022.10.04 00:25 신고

    풀지 못해서 정말 좋은 참고가 된 것 같네요! 감사합니다!
    한 가지 의문점이 첫 번째 while 문에서 start++, end--를 해줘야 하지 않을까요...?

    • Favicon of https://ifuwanna.tistory.com BlogIcon IfUWanna 2022.10.04 02:06 신고

      네 말씀 주신 내용이 맞습니다.
      코드를 옮겨올때 첫번째 while 문에서 조건 한줄이 누락되었네요.

      start++; end--;

      코드 수정해 두었습니다. -_-bb