[Leet Code] Matchsticks to Square

안녕하세요! 오늘은 6월 1주차 1번째 알고리즘인 Matchsticks to Square 풀이를 작성해보겠습니다.

---

문제

요약
주어진 matchsticks 로 사각형을 만들 수 있는지 여부를 true / false 로 return하는 문제입니다.
단, matchsticks 의 원소들은 길이를 자를 수 없습니다.

처음으로 생각한 방법

재귀호출 방식인 dfs 를 활용했습니다.
우선 사각형 한 변의 길이는 배열 원소들을 모두 더해서 4로 나눈 값으로 정합니다. 그 후 matchsticks 값을 더해가면서 한 변의 길이를 맞춥니다.
결과는 Accept!

이제 코드 설명에 들어가겠습니다.

---

코드 설명

boolean result = false;

return할 값인 result 변수를 설정합니다.

if (matchsticks == null || matchsticks.length < 4) return result;

만약 주어지는 배열이 null 이거나, matchstick 개수가 4 이하라면 사각형을 만들 수 없으므로 false 를 return 합니다.

int sum = 0;
for (int stick: matchsticks) {
    sum += stick;
}
if (sum % 4 != 0) return false;

이제 matchstick의 길이를 모두 합했을 때 사각형을 만들 수 있는지 여부를 확인합니다.
4로 나눴을 때 나머지가 발생하면 false 를 return 합니다.

Integer[] matchsticksArray = Arrays.stream(matchsticks).boxed().toArray(Integer[]::new);
Arrays.sort(matchsticksArray, Collections.reverseOrder());

matchstick 을 오름차순으로 정렬합니다.
Arrays.sort 를 사용하려면 Primitive 자료형을 Wrapper 클래스로 boxing 합니다.
그리고 reverseOrder 를 사용해서 오름차순으로 정렬합니다.

return dfs(matchsticksArray, new int[4], 0, sum / 4);

마지막으로 dfs 를 적용해서 return 해줍니다.

private boolean dfs(Integer[] matchsticks, int[] sums, int index, int target) {
    if (index == matchsticks.length) {
        if (sums[0] == target && sums[1] == target && sums[2] == target) {
            return true;
        }
        return false;
    }

    for (int i = 0; i < 4; i++) {
        if (sums[i] + matchsticks[index] > target) continue;
        sums[i] += matchsticks[index];
        if (dfs(matchsticks, sums, index + 1, target)) return true;
        sums[i] -= matchsticks[index];
    }

    return false;
}

dfs 함수는 위와 같습니다.
matchsticks , sums , target 을 인자로 받습니다.

만약 **matchsticks 에 접근할 index 값이 matchsticks.length 와 같다면 모두 접근한 것이므로 분기 처리**를 해줍니다.
sums 배열의 모든 값이 사각형 한 변의 길이를 뜻하는 target 과 값이 같다면 true 를 return 합니다.
그것이 아니라면 false 를 return 합니다.

아직 matchsticks 에 접근해야하는 경우라면 for 문을 순회하면서 sums 배열의 적절한 자리에 matchsticks 를 넣어가면서 dfs 를 재귀호출합니다.

전체 코드

class Solution {
    public boolean makesquare(int[] matchsticks) {
        boolean result = false;

        if (matchsticks == null || matchsticks.length < 4) return result;

        int sum = 0;
        for (int stick: matchsticks) {
            sum += stick;
        }
        if (sum % 4 != 0) return false;

        Integer[] matchsticksArray = Arrays.stream(matchsticks).boxed().toArray(Integer[]::new);
        Arrays.sort(matchsticksArray, Collections.reverseOrder());

        return dfs(matchsticksArray, new int[4], 0, sum / 4);
    }

    private boolean dfs(Integer[] matchsticks, int[] sums, int index, int target) {
        if (index == matchsticks.length) {
            if (sums[0] == target && sums[1] == target && sums[2] == target) {
                return true;
            }
            return false;
        }

        for (int i = 0; i < 4; i++) {
            if (sums[i] + matchsticks[index] > target) continue;
            sums[i] += matchsticks[index];
            if (dfs(matchsticks, sums, index + 1, target)) return true;
            sums[i] -= matchsticks[index];
        }

        return false;
    }
}

---

마무리

역시나 dfs 를 사용하는 문제는 생각을 조금 오랫동안 해야하는 것 같습니다!
이번 포스팅도 읽어주셔서 감사합니다 :)