Palindrome Partitioning

Palindrome Partitioning - LeetCode

★추후에 내가 짠 코드 최적화 해보기★

접근 방법 [필수 작성]

제한 조건 확인

• 대소문자 구분 우려 x
• 문자 사이 파티션바가 들어갈 수 있는 위치 15군데 총 2^15 가지의 경우의 수가 있을 수 있음
• 2^15 → 1024*32 → 약 33,000 가짓수 → 완전탐색으로 접근 가능

아이디어

1. 모든 파티션바를 넣을 수 있는 case를 재귀로 구현
2. 특정 파티션바를 넣은 경우에 각 substring 의 원래 순서와 뒤집은 순서가 같은지를 비교
   1. 같으면 answer 리스트에 추가
   2. 다르면 skip 후 다음 case 로 이동
3. answer 리스트 리턴

각 원소 사이에 ‘|’ 값을 추가할지 말지에 대한 케이스 재귀로 구현 → 이걸 구현하는 아이디어가 조금 어려웠음

결과로 나온 스트링을 ‘|’ 를 기준으로 split 후 각 원소들이 팰린드롬인지 확인

→ 여러개의 작은 기능함수들로 구분해서 구현함

코드 구현 [필수 작성]

# 2시5분 시작 -> 2시12분 중지 | 12시24분 재시작 -> 1시 06분 끝 | 총 49분 소요
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s) == 1:
            return [[s]]
        
        answer = []
        partition_bar = [True for _ in range(1,len(s))]
        #print(partition_bar)

        def make_subset(part_bar): #다양한 파티션바 존재 유무 정보를 입력
            subset_list = []
            stack = ""
            for i in range(len(part_bar)):
                stack += s[i]
                if part_bar[i]: #i번째 원소와 i+1번째 원소 사이에 파티션 바가 있으면
                    subset_list.append(stack) #subset_list 에 해당 string 추가
                    stack = ""
                else: #파티션 바가 없으면 이어서 stack 쌓기
                    pass
            stack += s[len(part_bar)]
            subset_list.append(stack)
            return subset_list
            
        def check_if_all_palindrome(sub_list):
            for i in range(len(sub_list)):
                if sub_list[i] != sub_list[i][::-1]:
                    return False
            return True

        def backtrack(start,part_bar):
            nonlocal answer
            #print(part_bar)
            subset = make_subset(part_bar)
            #print(subset)
            if check_if_all_palindrome(subset):
                answer.append(subset)
            for i in range(start,len(part_bar)):
                part_bar[i] = False
                backtrack(i+1,part_bar)
                part_bar[i] = True
        
        backtrack(0,partition_bar)

        return answer

배우게 된 점 [ 필수 X ]

[::-1] 에 대한 이해

해설코드와 내 코드의 차이

class Solution:
    def partition(self, s):
        if not s:
            return []
        lists = []
        partitions = []

        def backtrack(s, start, partitions, lists):
            if start == len(s):
                lists.append(partitions[:])
                return
            for i in range(start + 1, len(s) + 1):
                tmp_str = s[start:i]
                if tmp_str == tmp_str[::-1]:
                    partitions.append(tmp_str)
                    backtrack(s, i, partitions, lists)
                    partitions.pop()

        backtrack(s, 0, partitions, lists)
        return lists

나는 partition 을 나눌 수 있는 모든 경우의 수를 만들어 놓고 해당 조합의 원소들이 팰린드롬을 충족하는지 안하는지 조사했지만, 해설코드는 팰린드롬을 충족하는 경우의 수만 조합에 동적으로 추가해줌으로써 훨씬 간결하고 최적화된 코드를 보여주고 있다.

→ 어떻게 하면 간결하고 간단한 코드를 짜는 Thinking Process 를 가질 수 있을까?

질문 [ 필수 X ]

Q1.

→ 어떻게 하면 간결하고 간단한 코드를 짜는 Thinking Process 를 가질 수 있을까?

피드백 [ 코치 작성 ]

처음부터 간결한 코드를 작성하는 것은 누구에게나 힘든 일입니다. 제가 추천드리고 싶은 방법은 지금처럼 본인의 주관대로 코드를 작성한 후 본인의 코드를 수정하는 과정을 거치고 더 수정할 수 없다고 생각되면 다양한 솔루션 코드들을 보는 것입니다.

코드를 제출해서 통과했다는 것은 해당 문제에 대해 적절한 방법을 찾았다는 것입니다. 적절한 방법을 찾았다면 이후는 구현의 영역입니다. 구현은 처음부터 완벽할 수는 없기에 검토하고 수정하는 과정에서 보다 짜임새있고 간결한 코드가 됩니다.

솔루션 코드는 이 모든 과정을 마친 이후에 보는 것을 추천드립니다. 저는 솔루션 코드를 보는 것에 거부감을 갖지 않으셨으면 좋겠습니다. 해당 문제를 손도 대지 않은 상태에서 솔루션 코드를 보는 것은 물론 잘못된 행동이지만 문제를 푸는 과정에서 깊게 생각한 상태에서 솔루션 코드를 보는 것은 다양한 사람들의 시선과 접근 방법을 알 수 있게 해줍니다. 이러한 과정에서 인상깊은 코드들은 기억에 남게 되고 이후 문제를 풀 때 이러한 지식들이 큰 기반이 되어줄 것입니다.