[HackerRank] Palindrome Index - Python

Day 1 Interview Questions | HackerRank

플랫폼은 문제가 영어로 출시되는 HackerRank!

 

HackerRank는 신기하게 연습문제들에도 시간제한이 있다는 점이 좋은거 같아요. 👍🏻

하지만 개인적으로 프로그래머스에 비해 UI가 좋지 않아, 문제를 푸는데 어려움이 있었습니다. 😭

 

1. 문제

특정 index의 문자를 제거했을 때 Palindrome 문자열이 된다면, 해당 index를 반환합니다.

 

[입력]

문자열 s

 

[출력]

Palindrome을 만들 수 있는 index (* 업다면 -1 반환)

 

2. 풀이

문제를 풀어보니, 하나의 조건을 더 추가해줄 필요가 있는듯 합니다.

🌹 문자의 제거는 문자열의 앞 또는 뒤에서 하나씩 제거할 수 있다는 점입니다. 👍🏻

 

이러한 조건을 추가한다면 왼쪽과 오른쪽에서 시작하여, Palindrome 문자열을 만들때까지

왼쪽 point는 1씩 증가, 오른쪽 point는 1씩 감소하는 연산을 수행하면 됩니다. 

size = len(s)
left, right = 0, size-1

while left < right:
	left+=1
    right-=1

 

Palindrome은 좌우가 동일해야 하므로 s[left] == s[right]여야 한다는 점에 주목해야 합니다.

만약, 이 둘이 다를 경우 가장 앞에 문자(left) 또는 가장 뒤 문자(right)를 제거했을 때 해당 문자열이 Palindrome인지 검사해줄 필요가 있습니다.

 

앞에 문자(left)를 제거하였을 때 해당 문자열이 Palindrome이라면 left의 값을 반환하고,

뒤 문자(right)를 제거하였을 때 하당 문자열이 Palindrome이라면 right의 값을 반환해주어야 합니다.

if s[left] != s[right]:
	if isPalindrome(s, left+1, right): return left
    if isPalindrome(s, left, right-1): return right

 

3. 코드

def isPalindrome(s, left, right):
    if left == right: return False
    while left < right:
        if s[left] != s[right]: return False
        left+=1
        right-=1
    return True

def palindromeIndex(s):
    size = len(s)
    if size < 2: return -1
    
    left, right = 0, size-1
    if isPalindrome(s, left, right): return -1
    while left < right:
        if s[left] != s[right]:
            if isPalindrome(s, left+1, right): return left
            if isPalindrome(s, left, right-1): return right
        left+=1
        right-=1
    
    return -1