[LeetCode] 1601 - Maximum Number of Achievable Transfer Requests(java)

https://leetcode.com/problems/maximum-number-of-achievable-transfer-requests/

Maximum Number of Achievable Transfer Requests - LeetCode

요즘 리트코드 데일리문제를 계속 풀고 있다. 이유는 단순하게 문제의 질이 좋다. 

내가 생각하기에 좋은 문제는 문제 해석이 복잡한 것보다는 핵심 개념이 들어가며 이를 활용할 수 있는 문제이다.

 

핵심

이 문제는 Hard난이도지만, 그렇게 어려운 문제는 아니라고 생각한다. 아이디어는 한 사람씩 이동하면서 그때 빌딩의 사람수가 

초기의 수와 같은지 비교하면 된다.

 

 

정답 코드

class Solution {
    private int result = 0;
    private int[] building;

    public int maximumRequests(int n, int[][] requests) {
        building = new int[n];
        backTracking(requests, 0, n, 0);
        return result;
    }

    private void backTracking(int[][] requests, int index, int n, int count) {
        if (index == requests.length) {
            for (int i = 0; i < n; i++) {
                if (building[i] != 0) {
                    return;
                }
            }
            result = Math.max(result, count);
            return;
        }

        building[requests[index][0]]--;
        building[requests[index][1]]++;
        backTracking(requests, index + 1, n, count + 1);

        building[requests[index][0]]++;
        building[requests[index][1]]--;
        backTracking(requests, index + 1, n, count);
    }
}

해설

일반적인 백트래킹 문제이다. 중요한 점은 각각의 조건을 시행하거나, 안 하거나를 반복하며 전체를 탐색한다. 

시행할 경우 count를 1 올린다. 모든 조건을 탐색했다면 배열의 카운트가 전부 0 인지 확인한다.

전부 0일 경우 초기의 값과 동일하다는 의미이기 때문이다.

 

 

배운 점

일반적인 백트래킹문제라 그리 어렵지는 않았다.

초반에 영어로 되어있기에 문제해석이 어려웠지만 해석을 하니 쉽게 풀 수 있었다.

하지만 매우 중요한 개념을 담고 있는 문제라고 생각한다. 

아마 앞으로도 당분간 리트코드 문제를 풀 생각이다.