[해커랭크] Palindrome Index (C++)

문제 링크: www.hackerrank.com/challenges/palindrome-index/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

Palindrome Index | HackerRank

1. 주의할 점

- 삭제를 할 경우, 반으로 나눴을 때를 기준으로 왼쪽 or 오른쪽에 있는 원소를 삭제할 수 있다

- 어느쪽을 삭제해도 상관없는 경우를 조심한다(아래에 TC 존재)

#1
1
cbbcb
Answer : 4

 

2. 구현

- 왼쪽의 index를 L, 오른쪽의 index를 R로 나타내고, L과 R을 초기화한다

- Deleted 변수를 통해 1개의 원소를 삭제한 경험의 유무를 저장한다

- 삭제한다면 왼쪽, 삭제한다면 오른쪽 총 2가지의 방식으로 진행한다(시간복잡도: O(2*N/2) = O(N))

- 만약 비교하는 수가 같다면 안쪽으로 한칸씩 당긴다

- 만약 비교하는 수가 다르다면, 크게 2가지로 나눈다. 첫째, 이미 1개의 원소를 삭제한 적이 있는가? 있다면 Result = -1로 설정하고 While문을 벗어난다. 둘째, 삭제한 적이 없다면, 삭제하려는 원소 다음의 원소와 비교했을 때 같은가?

- 위에서 삭제한 원소의 Index를 Result에 저장한다

int palindromeIndex(string s) {
    int l=0,r=s.size()-1;
    int result = -1;
    bool deleted=false;
    //왼쪽 삭제
    while(l<=r){
        if(s[l]==s[r]){
            l++;
            r--;
        }
        else{
            if(deleted){
                result=-1;
                deleted = false;
                break;
            }
            if(s[l+1]==s[r]){       //같은 경우
                result = l;
                deleted = true;
                l+=2;
                r--;
            }
            else{       //다른 경우
                result = -1;
                break;
            }
        }
    }
    //오른쪽 삭제
    if(result==-1){
        l=0,r=s.size()-1;
        while(l<=r){
            if(s[l]==s[r]){
                l++;
                r--;
            }
            else{
                if(deleted){
                    result=-1;
                    break;
                }
                if(s[l]==s[r-1]){
                    result = r;
                    deleted = true;
                    l++;
                    r-=2;
                }
                else{       //다른 경우
                    result = -1;
                    break;
                }
            }
        }
    }
    return result;
}