https://leetcode.com/problems/palindrome-partitioning/description/
문제 파악
‘팰린드롬’ 이란 'eye', 'kayak', 'hannah' 처럼 거꾸로 읽어도 똑같은 문장이나 단어를 뜻한다. 뒤집어서도 같은 문자열이 나온다면 그것을 리턴해주면 될 것 같다.
접근 방법
나는 먼저 중간에 포기를 할 수 있는지 생각했다. 백트래킹을 통해 포기를 해서 최적화를 하기에는 끝까지 가봐야 아는 것들이라서 완전탐색으로 subsets 문제처럼 부분집합으로 얻을 수 있는 케이스들을 모두 짜고 뒤집어서 같은 것만 남기는 방식으로 코드를 짜볼 예정이다.
- 문자열이 주어짐
- 이를 순열로 만들고
- 모든 요소에 대해서 팰린드롬인지 (뒤집어도 똑같은지) 판별
- 모든 요소가 팰린드롬인 애들만 리턴
코드 구현
class Solution:
def partition(self, s: str) -> List[List[str]]:
# 기본 값 세팅
ans = []
new_ans = []
# 백트래킹 구현
def backtracking(start, curr):
ans.append(curr[:])
for i in range(start, len(s)):
curr.append(s[i])
backtracking(i + 1, curr)
curr.pop()
backtracking(0, [])
for i in range(len(ans)):
for j in range(len(ans[i])):
if ans[i][j] == ans[i][j][::-1]:
new_ans.append(ans[i][j])
print(new_ans)처음에는 이렇게 코드를 짜봤다. 내 생각에는 ans로 모든 부분 집합을 담고 반복문을 통해 밑에서 필터링하여 팰린드롬인 요소들만 new_ans에 추가해서 뽑아줬다. 하지만 이 코드는 문제가 있었다.
- 회문 검증: 부분 문자열이 회문인지 검사하는 부분이 잘못되어 있다. 단순히 한 글자씩 확인할 뿐 아니라, 실제로 전체 부분 문자열이 회문인지 확인해야 한다.
new_ans를 제대로 채우지 않음: 현재new_ans는 단지 회문인 단어만을 저장한다. 하지만, 문제에서 요구하는 것은 각 가능한 회문 분할 전체를 리스트로 반환하는 것이다.- 모든 부분 문자열을 저장: 현재의 코드는 단순히 모든 가능한 부분 문자열을 생성하고 저장하며, 이를 새 리스트
new_ans에 복사하려고 한다. 하지만 이 접근 방식은 불필요한 중복과 비효율성을 초래한다.
그렇기 때문에 먼저 팰린드롬을 만족하는지를 판별하는 함수(is_palindrome)을 만들고 이를 통해 새로운 new_ans를 쓰지 않고 자체적으로 백트래킹시 처리하게 설정해야겠다.
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = []
# 팰린드롬인지 판별하는 함수
def is_palindrome(sub: str) -> bool:
return sub == sub[::-1]
# 백트래킹 함수 구현
def backtracking(start, curr):
# base-case : 문자열의 끝에 도달하면, 현재까지 찾은 팰린드롬 분할을 결과에 추가
if start == len(s):
ans.append(curr[:])
return
# start부터 s의 끝까지 부분 문자열을 살펴본다.
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
# 부분 문자열이 팰린드롬인지 확인
if is_palindrome(substring):
# 현재 부분 문자열 추가
curr.append(substring)
# 문자열의 다음 부분으로 이동
backtracking(end, curr)
# 추가한 부분 문자열 pop -> 다음 반복 준비
curr.pop()
backtracking(0, [])
return ans먼저 백트래킹에 베이스 케이스를 추가해줬다. 현재 탐색 위치가 문자열 s의 끝에 도달했을 때 더 이상 분할할 문자열이 남아있지 않으므로 종료한다. 이 시점에서 curr 리스트에는 모든 가능한 부분 문자열이 회문인 경우만 포함되어 있을 것이다.
for end in range(start + 1, len(s) + 1) 루프를 통해 각 가능한 끝 지점에서 부분 문자열을 잘라내고, 이 부분 문자열이 회문인지 검사하여 분할한다. 현재의 부분 문자열이 회문이라면, curr에 추가하고, backtracking을 재귀적으로 호출하여 다음 부분 문자열을 찾는다.
배우게 된 점
- 범위 제한: for 루프에서
end가start + 1부터len(s) + 1까지 도는 이유는, 최소 길이 1 이상의 부분 문자열을 고려하고 있기 때문이다. - 불필요한 탐색 방지: 조건을 만족하지 않는 경우의 탐색을 피하는 방법을 배웠다. 나는 처음 코드에서는 조건에 대해서 이상하게 설정해서 애를 좀 먹었다.
