1727. Largest Submatrix With Rearrangements - Java

이번에 다룰 주제는 알고리즘 문제풀이 입니다. 제가 푸는 모든 문제들을 기록하진 않고, 풀면서 기록이 필요하다 싶은 문제들만 정리해서 기록하려고 합니다! 

 

해당 문제가 기록이 필요하다고 느낀 이유는 문제 해결을 위한 접근 방식을 기록해보고, 해당 접근 방식의 문제점과 해당 문제점을 해결하기 위해 어떤 접근 방식을 생각해 내야 하는지를 기록함으로써 제가 어려워 하는 부분들을 찾아낼 수 있기 때문입니다.

 

이제 문제를 살펴보겠습니다.

 

문제

https://leetcode.com/problems/largest-submatrix-with-rearrangements/

Largest Submatrix With Rearrangements - LeetCode

 

 

 

m X n 2차원 배열이 주어지면 해당 배열의 열 만 이동하여 만들 수 있는 최대 부분 행렬을 찾는 문제입니다.

그래서 위 행렬의 답은 4가 됩니다.

 

문제 해결 접근 방식

각 열의 모든 1들을 더해서 배열에 저장. 그리고 그 배열을 내림차순 정렬 후 부분 행렬 찾기

 

문제점

이 방식의 문제점은 열만 재배치 할 수 있다는 조건을 무시했다는 점 이었습니다.

문제를 직접적으로 알 수 있는 예시를 한번 보겠습니다.

count[i] 배열에는 차례대로 2 1 2 가 담겨지고 내림차순 정렬 후 2 2 1 이 되어 최대 부분 행렬을 구하게 되면 결과는 4입니다. 하지만 실제로 답은 1 입니다.

 

위 방식의 근본적인 문제점은 count 배열을 만드는 과정에서 행 이동될 수 있다는 점 입니다.

 

문제 해결 접근 방식 2

각 열에서 1의 연속성을 파악하기 위한 prefix sum 배열(2차원 배열)을 만들어 줍니다.

prefix sum 배열의 각 행마다 내림차순을 해준 후 최대 부분 행렬을 구해줍니다.

 

문제의 첫번째 예시 2차원 배열에 해당 문제 해결 방식을 적용해 보겠습니다.

 

그림의 이해를 돕기 위해 count 배열의 한 행을 가져와 보겠습니다.

count 배열의 1행을 한번 보겠습니다.

1 2 1

즉 이건 0행부터 1행까지 각 열의 연속된 1의 개수를 의미합니다.

 

count[1] 행은 1 1 2 이긴 하지만 문제에서 열 배치는 허용했으므로 결국 같습니다.

처음 문제 해결 접근 방식과 달리 이번 방식은 1의 연속성을 보장합니다. 그렇기 때문에 이 상태에서 최대 부분 행렬을 구해도 괜찬습니다.

 

이 방식을 각 행마다 반복해주면 됩니다.

 

코드

class Solution {
    public int findLargestSubmatrix(int width, int seqOneNum){
        return width * seqOneNum;
    }
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        //Matrix에 prefix sum 덮어쓰기!
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0) matrix[i][j] = 0;
                else matrix[i][j] += matrix[i-1][j];
            }
        }
        int res = 0;
        //prefix sum 배열의 각 행을 방문하여 최대 부분 수열 찾기!
        for(int i=0;i<m;i++){
            Integer[] tmp = Arrays.stream(matrix[i]).boxed().toArray(Integer[]::new);
            Arrays.sort(tmp,Comparator.reverseOrder());
            for(int j=0;j<n;j++){
                res = Math.max(res,findLargestSubmatrix((j+1),tmp[j]));
            }
        }

        return res;
    }
}

 

 

마무리

처음에는 굉장히 복잡한 방식으로 접근했었습니다. 하지만 문제의 hint를 통해 좀 더 간단하게 문제에 접근할 수 있었습니다. prefix sum을 어떻게 만들어야 할지 고민도 많이 했고, 이 과정에서 제가 간단하고 효율적인 변수 설정을 통해 문제를 해결하는 역량이 많이 부족함을 느꼈습니다...