둔필승총

https://www.acmicpc.net/problem/17609

[문제 정의]

이 문제는 회문을 판단하는 것 이외에 유사 회문이라는 것을 정의하였다. 회문은 앞뒤가 똑같은 단어이고, 유사 회문은 회문이 아닐경우 단어 하나만 제외하면 회문이 되는 단어를 말한다. 그럼 경우가 3가지를 구분하여 정답을 출력해주면 되는 문제였다.

[풀이]

1. [잘못된 풀이] : 처음에 생각한 풀이는 문자열의 맨 앞 단어와 맨 뒤의 단어를 없애버리면서 하나씩 고려하는게 좋다고 생각하였다. 그래서 맨 앞의 단어와 맨 뒤의 단어가 같으면 파이썬 list에 있는 pop함수를 이용하여 제외시켰다. 

그리고 만약 앞 뒤의 단어가 다르다면 경우를 2개로 나눈다. 남은 단어의 젤 앞을 제외하는 경우와 젤 뒤를 제외하는 두 개의 case로 나누어서 해당 단어를 다시 회문인지 아닌지 판단하여 해당 단어가 회문이면 결국에 처음에 제공된 문자열은 유사회문인 것이다. 

import sys
input = sys.stdin.readline
T = int(input())
letterlist = []
answers = []
for i in range(T):
    letter = list(input())
    letterlist.append(letter[:-1])
for letter in letterlist:
    left = 0
    right = len(letter) - 1
    answer = 2
    while True:
        if letter[left] == letter[right]:
            letter.pop(right)
            letter.pop(left)
            right = len(letter) - 1
            if len(letter) == 0 or len(letter) == 1:
                answer = 0
                break
        elif letter[left] != letter[right]: # 다른 경우
            temp1 = letter[left + 1:right + 1]
            if temp1[:] == temp1[::-1]:
                answer = 1
                break
            else:
                temp2 = letter[left:right]
                if temp2[:] == temp2[::-1]:
                    answer = 1
                break
    answers.append(answer)
for answer in answers:
    print(answer)

위의 풀이는 예제는 맞지만, 시간 초과가 나는 코드이다. 어느 부분이 문제인지 몰랐었는데 pop이 문제였다. 맨 앞의 단어를 pop하는 경우는 시간 복잡도가 O(1)이라서 괜찮았지만 문자열 맨 뒤의 단어를 pop하는 경우는 O(n)이 될 수 있어서 시간초과가 나는 것이였다.

그래서 해당 코드를 비슷하게 유지하되 pop시키지 않고 비교만 하는 코드로 바꾸었다.

[정답]

import sys
input = sys.stdin.readline

T = int(input())
letterlist = []
answers = []

for i in range(T):
    letter = list(input())
    letterlist.append(letter[:-1])


for letter in letterlist:
    left = 0
    right = len(letter) - 1
    answer = 2
    while True:
        if letter[left] == letter[right]:
            letter.pop(right)
            letter.pop(left)
            right = len(letter) - 1
            if len(letter) == 0 or len(letter) == 1:
                answer = 0
                break
        elif letter[left] != letter[right]: # 다른 경우
            temp1 = letter[left + 1:right + 1]
            if temp1[:] == temp1[::-1]:
                answer = 1
                break
            else:
                temp2 = letter[left:right]
                if temp2[:] == temp2[::-1]:
                    answer = 1
                break
    answers.append(answer)

for answer in answers:
    print(answer)