맞왜틀 기록하기 ~
https://www.acmicpc.net/problem/17609
투포인터를 활용해서 풀 수 있다.
처음부터 회문 통과면 0,
그게 아니라면 하나씩 좁혀가며 왼쪽 끝을 제거한 결과와, 오른쪽 끝을 제거한 결과끼리 비교할 수 있다.
둘 다 안 되는 경우 2를 반환하면 된다.
def solution():
S = input()
# 투포인터
res = 0 # 삭제 없이 완전한 회문인가?
s, e = 0, len(S) - 1
while s < e:
if S[s] == S[e]:
s += 1
e -= 1
else:
if res == 1: # 이미 한번 삭제 거친 경우
res = 2
break
res = 1
# 왼쪽 삭제 츄라이 ~
if s + 1 < e and S[s + 1] == S[e]:
s += 2
e -= 1
# 오른쪽 삭제 츄라이 ~
elif e - 1 > s and S[s] == S[e - 1]:
s += 1
e -= 2
else:
res = 2
break
return res
# 입력부
t = int(input())
for _ in range(t):
print(solution())
끝에서부터 줄여가며 끝과 끝 글자를 비교하며 업데이트 하는 방식이다.
한동안 여기서 크게 벗어나지 못한채 맞왜틀을 부르짖고 있었다.
그러다 발견한 빛과 소금같은 반례 .. 🥹✨
- "aapqbcbqpqaa"
"pqbcbqpq" -> 여기서 복병인 게, 이 코드에 의하면 "pqbcbqp"도, "qbcbqpq"도 일단 통과하기 때문이다. (조건문 순서에 의해 "qbcbqpq"가 통과해버린 것 -> 2가 나온 것)
그제서야 한쪽 끝을 짤랐을 때, 회문인지 판별하고 끝내야하는구나 깨달았다.
def solution():
S = input()
# 완전한 회문인가?
if S == S[::-1]:
return 0
# 1인가 2인가 -> 투포인터
s, e = 0, len(S) - 1
while s < e:
# 불일치 하는 자리 찾을 때까지 좁혀 가기
if S[s] == S[e]:
s += 1
e -= 1
else:
# 양쪽 끝 삭제 츄라이 ~ !
ltmp, rtmp = S[s + 1: e + 1], S[s: e]
if ltmp == ltmp[::-1] or rtmp == rtmp[::-1]:
return 1
else:
return 2