[백준 17609] 회문

실패 과정

# 회문 검사 함수
def Check(s):
  for i in range(len(s) // 2):
    if(s[i] != s[len(s) - i - 1]):
      return False

  return True
  
# 문자열 입력받기
t = int(input())
strings = []

for _ in range(t):
  strings.append(input())

# 각 문자열마다 Check 돌려보고 안되면 문자열 하나씩 빼보기
for i in range(t):
  if(Check(strings[i]) == True):
    print(0)
  else:
    isValid = False
    for j in range(len(strings[i])):
      removed = strings[i][:j] + strings[i][j+1:]
      if(Check(removed)):
        isValid = True
        break
    if(isValid):
      print(1)
    else:
      print(2)
      
        
        

문제에서 주어진대로, 만약 회문 검증이 실패하면 그 문자열의 모든 문자를 하나씩 빼 보면서 회문 검증을 다시 돌렸다.

사실 풀면서도 문자열 길이가 100,000까지란 조건을 보고 예상은 했으나...

역시 어림도 없었다. 그럼 어떻게 연산을 줄일 수 있을까? 생각해본건

회문 검증 함수 자체에서 회문 검증에 실패할 경우, 스킵을 해보자!

였다. 왼쪽에서 문자열을 스킵해보고, 안되면 오른쪽에서 스킵해보고, 둘 다 실패할 경우 회문이 아닌 것으로 처리하면 될 것 같았다.

이렇게 하면 굳이 문자열을 직접 빼서 처음부터 다시 돌려볼 필요가 없으니, 연산량이 많이 줄어들 것으로 예상했다.

최종 코드

# 회문인지만 판단
def Check(s):
  for i in range(len(s) // 2):
      if(s[i] != s[len(s) - 1 - i]):
          return False
  return True

# 스킵 포함하여 Check 호출
def isPal(s):
  for i in range(len(s) // 2):
    if(s[i] != s[len(s) - 1 - i]):
      left = Check(s[i + 1 : len(s) - i])   # 왼쪽
      right = Check(s[i : len(s) - i - 1])   # 오른쪽
      if(left or right):
        return 1
      else:
        return 2
  return 0
  
# 문자열 입력받기
t = int(input())
strings = []

for _ in range(t):
  strings.append(input())

# 각 문자열마다 Check 돌려보기
for i in range(t):
  print(isPal(strings[i]))
        

왼쪽 스킵 후 Check 호출, 오른쪽 스킵 후 Check 호출하여 하나라도 성공 시 1을 반환하고 실패 시 2를 반환하도록 했다.