문제
Baekjoon17609: 회문
- 설명: 주어진 문자열이 그 자체로 회문이면 $0$, 한 문자를 삭제했을 때 회문이면 $1$, 회문이 아니라면 $2$를 출력하라.
풀이
접근
- 문제를 보고 다음과 같은 재귀 구조를 생각해냈다.
- 먼저 용어 정의를 하자면
str은 주어진 문자열이고, left, right는 각 문자열의 양 끝이다.
- 주어진
str[left]과 str[right]이 같다면
str[left + 1 ~ right - 1]의 회문 여부가 주어진 문자열의 결과이다.
- 만약 다르다면
str[left ~ right - 1], str[left + 1 ~ right] 중 회문이 있다면 답은 $1$이다.- 주어진 문자열의 양 끝이 다른데 이미 한 문자를 삭제했었다면 주어진 문자열은 회문이 아니다. ($2$를 반환한다.)
- 위의 로직대로 코드를 작성하였지만 재귀가 분기되는 구문이 있어서 시간 초과가 날 것 같았다.
- 하지만 곰곰히 생각해보면 또 될 것 같다고 생각해서 일단 제출을 하였고 정답이었다.
증명
- 위 처럼 이전까지 어떤 문자도 삭제하지 않았고 주어진 문자열의 양쪽 끝이 다를 때 분기를 해서 뭔가 전형적인
DP의 구조처럼 보인다.
- 하지만 문자열이 $100,000$이기 때문에 $2$차원 테이블을 만들 수 없으므로 쉽사리
DP를 적용하기 어렵다.
- 그렇다면 어떻게 위의 로직이 시간초과를 내지않고 통과할 수 있었을까?
- 분기가 딱 한번만 이뤄지기 때문에 가능하다.
- 즉, 위의 로직은 최대 한 문자만을 삭제할 수 있기 때문에 중복이 발생하더라도 시간복잡도는 최대 $O(n)$이다. ($n$은 문자열의 길이)
- 분기가 되는 부분은 오직 양쪽 끝이 다른 문자이고 이전에 문자를 삭제한 적이 없을 때이다.
- 이때 $2$가지로 분기 되지만 $1$번 분기된 이후로는 양 끝이 다를 때 또 분기하는 것이 아니라 $2$를 반환한다.
- 또한 처음 분기되는 지점은 양쪽 끝을 지속적으로 비교하며 처음으로 달라지는 부분이다.
- 우리는 회문을 판단하는 것이기 때문에 중간에 한 문자라도 다르면 회문이 아니고,
- 이때 유사 회문이라도 찾아야하기 때문에 일단 현재 찾은 다른 문자를 처리해주어야한다.
- 따라서 중간 중간 다른 부분이 많아(
abcd처럼) 모든 부분에서 분기가 이루어지는 것 아니냐라는 생각이 들 수도 있지만
- 가장 끝 부분이 다르면 애초에 회문이 될 수 없으므로 양쪽 끝에서 처음으로 달라지는 부분에서 유사 회문을 판별해야 조건을 만족할 수 있다.
- 결론적으로 위에 언급한 로직은 분기가 딱 1번 이루어지기 때문에 문자열을 최대 $2n$번 탐색한다.
오늘의 회고
- 누가봐도 안될 것 같았지만 또 뭔가 직관적으로 생각해보면 될 것 같아서 제출했더니 맞았다.
- 문제 이런식으로 풀면 안되는데..!
- 그래도 엄밀하진 않지만 Proof of Solving도 가끔 가끔 하는 것이 오히려 문제를 빨리 풀 수 있어서 PS나 코테 분야에서 아예 도움이 되지 않는건 아닌 것같다 ㅎ
Code
# Baekjoon17609.py
import sys
sys.setrecursionlimit(100_000)
def solve(string: str, left: int, right: int, is_deleted: bool) -> int:
if left >= right:
return 1 if is_deleted else 0
else:
if string[left] == string[right]:
return solve(string, left + 1, right - 1, is_deleted)
else:
if not is_deleted:
return min(
solve(string, left + 1, right, True),
solve(string, left, right - 1, True)
)
else:
return 2
n = int(input())
for _ in range(n):
str1 = input()
print(solve(str1, 0, len(str1) - 1, False))