백준_17609 (회문_실버1_문자열_팰린드롬)

• 링크 : https://www.acmicpc.net/problem/17609

---

메모한 것

이거그냥 팰린드롬 확인하는 함수 만들어서
브루트포스로 하나 할 때마다 함수로 체크하면 되는 거 아님?

---

솔루션코드 - 시간초과

• 이렇게 짜는건 오래 안걸렸는데 시간초과가 뜸
  • 슬라이싱이 O(N)걸려서 그런듯

def is_palindrome(a):
    if a == a[::-1]:        return True
    else:        return False

for _ in range(int(input())):
    text = input()
    is_not = True
    
    if is_palindrome(text):
        print(0)
        continue
    
    leng = len(text)
    for i in range(leng):
        if is_palindrome(text[:i]+text[i+1:]):
            print(1)
            is_not = False
            break
            
    if is_not:            
        print(2)
        is_not = True

---

솔루션코드2 - 시간초과

• 깊은복사 (copy.deepcopy()) 했는데도...
  • 결국 is_palindrome()에 [::-1]가 문제인거
  • 다른 블로그 솔루션 코드 보니까 이거 이렇게 안함(직접구현함)

import copy

def is_palindrome(a):
    if a == a[::-1]:        return True
    else:        return False

for _ in range(int(input())):
    text = list(input())
    is_not = True
    
    if is_palindrome(text):
        print(0)
        continue
    
    leng = len(text)
    for i in range(leng):
        
        tmp = copy.deepcopy(text)
        del tmp[i]
        
        if is_palindrome(tmp):
            print(1)
            is_not = False
            break
            
    if is_not:            
        print(2)
        is_not = True

---

솔루션 코드 - 블로그

• 팰린드롬을 직접 구현했음 (중요)

def is_palindrome(word, left, right):
    while (left < right):
        if (word[left] == word[right]):
            left += 1
            right -= 1
        else:
            return False
    return True

print(is_palindrome('abba', 0, len('abba')-1))
print(is_palindrome('xabba', 0, len('xabba')-1))
print(is_palindrome('xabbay', 0, len('xabbay')-1))

• 그래서 정답 코드는 다음과 같음
  - 출처 : https://kkk4872.tistory.com/143

import sys

def secondCheck(word,left,right):
    while (left < right):
        if (word[left] == word[right]):
            left += 1
            right -= 1
        else:
            return False
    return True


def firstCheck(word,left,right):
    while (left < right):
        if (word[left] == word[right]):
            left += 1
            right -= 1
        else:
            check1 = secondCheck(word,left+1,right)
            check2 = secondCheck(word,left,right-1)
            if(check1 or check2):
                return 1
            else:
                return 2
    return 0

n = int(sys.stdin.readline().rstrip("\n"))
for _ in range(n):
    word = sys.stdin.readline().rstrip("\n")
    left=0
    right=len(word)-1
    ans = firstCheck(word,left,right)
    print(ans)