Matchsticks to Square

문제 링크 : https://leetcode.com/problems/matchsticks-to-square/

Matchsticks to Square - LeetCode

문제 해설 : 성냥의 길이가 저장된 배열이 주어집니다. 성냥은 부러뜨릴 수 없지만 이어붙일 수는 있습니다. 모든 성냥을 한 번씩 사용하여 정사각형을 만들 수 있으면 True를, 그럴 수 없으면 False를 반환하세요. 

 

제한 사항

1) 1 <= matchsticks.length <= 15

2) 0 <= matchsticks[i] <= 10^9

 

 

성냥을 부러뜨릴 수 없고 모든 성냥을 사용해야 하므로

성냥을 모두 사용해서 정사각형을 만들기 위해서는 성냥 전체의 길이가 4의 배수여야 합니다.

total = sum(matchsticks)
if total % 4 > 0:
	return False

 

성냥의 개수가 15개 이하인 점에 착안하여

성냥을 놓는 모든 경우를 확인하는 함수를 작성했습니다.

def pick(self, cur: int, length: int, matchsticks: List[int], check: List[bool]) -> bool:
    if cur == length:
        return True

    for i in range(len(matchsticks)):
        if check[i]:
            continue
        elif matchsticks[i] + cur > length:
            continue
        else:
            check[i] = True
            if self.pick(cur + matchsticks[i], length, matchsticks, check):
                return True
            check[i] = False
    return False

cur : 선택된 성냥의 총 길이

length : 정사각형의 한 변의 길이

matchsticks : 성냥의 정보가 저장된 List

check : 성냥의 선택 여부가 저장된 List

 

반복문을 수행하면서 선택되지 않은 성냥을 고릅니다.

해당하는 성냥과 cur를 더했을 때 정사각형의 한 변의 길이보다 크지 않다면

해당 성냥을 선택하고 cur이 정사각형의 한 변의 길이와 같아질 때까지 재귀함수를 수행합니다.

 

어떤 방법으로든 성냥을 선택해서 length만큼의 길이를 만들어낼 수 있다면

True를 반환하고 그렇지 않으면 False를 반환합니다.

 

 

def makesquare(self, matchsticks: List[int]) -> bool:
    total = sum(matchsticks)
    if total % 4 > 0:
        return False
    
    length = total // 4
    
    matchsticks.sort(reverse=True)
    check = [False for i in range(len(matchsticks))]

    for i in range(4):
        if self.pick(0, length, matchsticks, check) == False:
            return False
    
    return True

pick 함수를 4번 수행하는 동안 모두 True를 반환한다면 한 변의 길이가 length인 정사각형을 만들 수 있음을 알 수 있습니다. 따라서 True를 반환합니다.

 

모든 성냥을 사용했는지 확인하는 코드는 필요 없습니다.

이미 모든 성냥의 길이의 합을 4로 나눈 length를 알고 있기 때문에 length를 4번 구할 수 있음이 증명되면

모든 성냥을 사용했음이 명확하기 때문입니다.

 

 

아래는 전체 코드입니다.

from typing import List

class Solution:
    def pick(self, cur: int, length: int, matchsticks: List[int], check: List[bool]) -> bool:
        if cur == length:
            return True

        for i in range(len(matchsticks)):
            if check[i]:
                continue
            elif matchsticks[i] + cur > length:
                continue
            else:
                check[i] = True
                if self.pick(cur + matchsticks[i], length, matchsticks, check):
                    return True
                check[i] = False
        return False


    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 > 0:
            return False
        
        length = total // 4
        
        matchsticks.sort(reverse=True)
        check = [False for i in range(len(matchsticks))]

        for i in range(4):
            if self.pick(0, length, matchsticks, check) == False:
                return False
        return True