[LeetCode] Matchsticks To Square

문제링크

Matchsticks to Square - LeetCode

 

matchstick이 담긴 배열 matchsticks가 주어질때 모든 matchstick을 사용하여 하나의 정사각형을 만드는 문제

조건1. stick은 부술수 없고 연결할 수 있다.
조건2. 각각의 stick은 한번만 사용할 수 있다. 

접근방법

우선 정사각형이 될 수 있는 조건을 판별해야한다.
perimeter : 모든 성냥깨비 길이의 합
sideLen : perimeter / 4 (한변의 길이)

const perimeter = matchsticks.reduce((acc, cur) => acc += cur);
const sideLen = perimeter / 4;

matchsticks.sort((a, b) => b - a);

if(!Number.isInteger(sideLen) || matchsticks.length < 4 || matchsticks[0] > sideLen) return false;​

한변의 길이가 정수가 아니거나, 성냥깨비의 개수가 3개 이하이거나, 가장 긴 성냥깨비가 한변의 길이보다 긴 경우
정사각형이 될 수 없다.

이제 모든 성냥깨비를 통해 정사각형이 될 수 있는지 (4개의 sideLen을 만들 수 있는지)를 구해야한다.

bfs방식으로 가까운 성냥부터 탐색하여 진행하였다.
sideArr : 정사각형 4변을 의미 (모든 변의 길이가 sideLen이 되어야함)

const sideArr = new Array(4).fill(0);

const dfs = (stickIdx, sideLen) => {
    if(stickIdx === matchsticks.length) return true;
    for(let i = 0; i < 4; i++){
        if(sideArr[i] + matchsticks[stickIdx] > sideLen) continue;

        sideArr[i] += matchsticks[stickIdx];

        if(dfs(stickIdx + 1, sideLen)) return true;

        sideArr[i] -= matchsticks[stickIdx];
    }

    return false;
}​

함수는 첫번째 성냥부터 탐색하며 조건에 맞는 sideArr[i]에 성냥을 넣는 방식으로 진행한다.

예)
matchsticks = [10,7,7,7,2,2,2,1,1,1] (내림차순 정렬)
sideArr = [0,0,0,0]
sideLen = 10;

sideArr[i] + matchsticks[stickIdx]  > 10 인 경우 sideArr[i+1]에 matchsticks[stickIdx]를 더하며 진행
dfs(0, sideLen) 실행시 => sideArr[10, 0, 0, 0]
재귀를 통해 dfs(1, sideLen) 실행시 => sideArr[10, 7, 0, 0]
재귀를 통해 dfs(2, sideLen) 실행시 => sideArr[10, 7, 7, 0]
재귀를 통해 dfs(3, sideLen) 실행시 => sideArr[10, 7, 7, 7]
재귀를 통해 dfs(4, sideLen) 실행시 => sideArr[10, 9, 7, 7]
...
재귀를 통해 dfs(9, sideLen) 실행시 => sideArr[10, 10, 10, 10]
stickIdx === matchsticks.length가 되었으므로 true를 반환한다.

이는 제일 간단한 경우를 설명한 것으로 만약 false가 호출되어 sideArr[i] -= matchsticks[stickIdx];가 실행되면 설명하기 매우 복잡해진다.

 

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function(matchsticks) {
    const perimeter = matchsticks.reduce((acc, cur) => acc += cur);
    const sideLen = perimeter / 4;
    const sideArr = new Array(4).fill(0);
    
    matchsticks.sort((a, b) => b - a);
    
    if(!Number.isInteger(sideLen) || matchsticks.length < 4 || matchsticks[0] > sideLen) return false;
    
    const dfs = (stickIdx, sideLen) => {
        if(stickIdx === matchsticks.length) return true;
        for(let i = 0; i < 4; i++){
            if(sideArr[i] + matchsticks[stickIdx] > sideLen) continue;
            
            sideArr[i] += matchsticks[stickIdx];
            
            if(dfs(stickIdx + 1, sideLen)) return true;
            
            sideArr[i] -= matchsticks[stickIdx];
        }
        
        return false;
    }
    
    return dfs(0, sideLen)
};