[리트코드] 473. Matchsticks to Square

문제 분석

Matchsticks to Square

문제 자체는 심플하다.
그래서 성냥개비 길이의 리스트가 있으면 해당 성냥개비로 정사각형을 만들 수 있는지 없는지 판별하는 알고리즘을 짜면 된다.

그래서 처음에는 정렬+조합+브루트포스를 이용해서 안되는 경우 바로 False를 반환하는 방식을 하려했지만,

[1, 1, 1, 1, 2, 3, 3, 4 ]

다음과 같이 정렬된 경우 실제 답은 True지만 위와 같은 방식으로 했을 때에는
(1+1+1+1), (2...)->False가 나오게 된다.

따라서 단순한 조합이 아니라 하다가 안되면 전으로 돌아가는, 백트래킹이 필요하다.

이번 글에서 백트래킹에 대한 설명을 하진 않을 것이다!

혹시나 궁금하다면

코드

'''
473. Matchsticks to Square
https://leetcode.com/problems/matchsticks-to-square/
'''

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        size, one_side = len(matchsticks), sum(matchsticks)/4
        matchsticks.sort(reverse=True)

        # 트래킹 돌리기 전에 파악할 수 있는 조건
        # 1. 개수 합이 4로 나눠떨어지지 않을 때
        # 2. 가장 큰 성냥개비가 한 변의 길이를 넘을 때
        if one_side != int(one_side) or matchsticks[0] > one_side:
            return False
        
        # index: 성냥개비 리스트의 인덱스
        # space: 한 변에다가 한 개씩 갖다 넣으면서 남은 길이
        # confirmed: 몇 개의 변이 만들어지기로 확정됐는지
        def tracking(index, space, confirmed):
            if confirmed == 3:
                return True
            while index < size:
                cur_match = matchsticks[index]

                # 현재 성냥개비가 남은 길이보다 클 때 다음 인덱스의 것으로 넘기기
                # 
                if cur_match > space:
                    index += 1
                    continue

                # 이걸로 만들 것으로 확정됐으면, 해당 성냥개비 아웃시키기
                matchsticks[index] = one_side + 1

                # 한 변 만들 때 현재 성냥개비가 딱 맞을 때
                if cur_match == space:
                    result = tracking(1, one_side, confirmed + 1)
                else:
                    result = tracking(index+1, space-cur_match, confirmed)
                
                if result:
                    return True

                # 끝까지 검사해도 맞는 성냥개비가 없으면 되돌려놓기
                matchsticks[index] = cur_match

                # 검사하는 성냥개비가 같은 것은 뛰어넘기
                while index < size and matchsticks[index] == cur_match:
                    index += 1
            return False
        return tracking(0, one_side, 0)

'''
Runtime: 86 ms, faster than 97.42% of Python3 online submissions for Matchsticks to Square.
Memory Usage: 14 MB, less than 57.39% of Python3 online submissions for Matchsticks to Square.

'''