[#17609] 회문

문제

#17609 회문
Gold5
적용 알고리즘: X (String)

---

풀이 방법

• Brute Force 알고리즘으로 풀면 시간 초과가 남
• 회문 검사를 하는 동시에 유사회문인지도 검사해야 함
• 문자의 양쪽 끝에서부터 시작하여 해당 위치 인덱스의 문자가 동일한지 판단
• 동일하지 않다면 두 문자중 하나를 뺐을 때 각각 회문인지 판단

코드 흐름

1. 특정 문자에 대해서 반복문을 0에서 해당 문자의 길이 // 2까지 반복문을 돌린다.
2. 문자의 중앙을 기준으로 문자 양쪽에서 동일한 위치에 있는 문자에 대해 동일함을 검사한다. 만약 틀린경우, 유사회문 검사(단계 3)를 실시한다.
3. 유사회문 검사
   1. 왼쪽 문자를 뺀 문자와 오른쪽 문자를 뺀 문자를 준비한다.(temp1, temp2)
   2. 양쪽의 인덱스를 기준으로 이미 바깥쪽은 회문 인증이 되었으니 현재 문자의 인덱스의 안의 문자에 대해서 회문 검사를 실행한다. 이를 temp1, temp2에 대해서 각각 한번씩 실행한다.
   3. 회문 검사를 실행해서 만약 틀린 경우, 이는 회문도 아니고 유사 회문도 아니다. 2를 출력한다.
   4. 만일 검사를 통과한 경우, 이는 유사회문 문자이다. 1을 출력한다.
4. 2의 과정에서 일치하지 않는 문자가 없다면 이는 회문이다. 0을 출력한다.

코드

처음 시도했던 Brute Force 방법(시간초과)
해당 문자가 회문인지 검사하고, 회문이 아닌 문자에 대해서 유사회문 검사.(이러는 경우 유사회문 검사에서 회문 검사를 다시 실행하기 때문에 시간초과 발생)

# 회문이면 1 리턴, 회문이 아니면 0리턴
def is_palindrome(text):
    for i in range(len(text) // 2):
        if (text[i] != text[-i -1]):
            return 0
    return 1

# 유사회문일 경우 1 리턴, 아닌 경우 0 리턴
def is_pseudo_palindrome(text):
    for i in range(len(text)):
        temp = text
        temp = list(temp)
        temp[i] = ""
        temp = "".join(temp)
        if (is_palindrome(temp)):
            return 1
    return 0

n = int(input())

for i in range(n):
    text = input()
    if (is_palindrome(text)):
        print("0")
    else:
        if (is_pseudo_palindrome(text)):
            print("1")
        else:
            print("2")

회문 검사를 진행하는 동시에 유사 회문 검사

def is_palindrome(text):
    for i in range(len(text) // 2):

        # 유사회문인지 탐색
        if (text[i] != text[-i -1]):

            flag = 0    # 0이면 유사회문이 아님
            # 중앙을 기준으로 왼쪽 문자 제거
            temp1 = text
            temp1 = list(temp1)
            temp1[i] = ""
            temp1 = "".join(temp1)

            # 중앙을 기준으로 오른쪽 문자 제거
            temp2 = text
            temp2 = list(temp2)
            temp2[-i -1] = ""
            temp2 = "".join(temp2)

            # 뺀 문자가 회문인가? (왼쪽을 뺀 경우 검사)
            for j in range(i, len(temp1) // 2 + 1):
                if (temp1[j] != temp1[-j -1]):
                    break
                if (j == len(temp1) // 2):
                    flag = 1
            
            # 오른쪽을 뺀 경우 검사
            if (flag == 0):
                for j in range(i, len(temp2) // 2 + 1):
                    if (temp2[j] != temp2[-j -1]):
                        break
                    if (j == len(temp2) // 2):
                        flag = 1
            
            if (flag == 1):
                return 1        # 유사회문
            else:
                return 2        # 회문도, 유사회문도 아님
    return 0


n = int(input())

for i in range(n):
  text = input()
  print(is_palindrome(text))

체감 난이도: 3.9/5
처음에 BF로 했는데 당연히 시간초과가 났다. 회문 검사를 하고 만약 아닐 경우에 유사회문 검사로 들어가서 그 안에서도 모든 문자에 대해서 회문 검사를 하는… 방식이었는데 시간초과가 날 만하다.
그래서 고안한 두 번째 방식이 회문 검사를 실시하는 도중에 유사회문을 검사하는 것이었다. 근데 이것도 솔직히 시간초과가 나지 않을까 했는데 무사히 통과하였다.

---

[문자열 특정 인덱스 제거하기]
리스트로 변환했다가 제거하고 다시 붙이기

temp1 = text
temp1 = list(temp1)
temp1[i] = ""
temp1 = "".join(temp1)