[LeetCode] - 1252. Cells With Odd Values in a Matrix

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Cells with Odd Values in a Matrix" 문제입니다.

--> https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/description/

 

문제 : 

There is an m x n matrix that is initialized to all 0's.

There is also a 2D array indices where each indices[i] = [ri, ci] represents a 0-indexed location to perform some increment operations on the matrix.

For each location indices[i], do both of the following :

• Increment all the cells on row ri.
• Increment all the cells on column ci.

Given m, n, and indices, return the number of odd-valued cells in the matrix after applying the increment to all locations in indices.

---

Example 1 :

Input : m = 2, n = 3, indices = [[0,1],[1,1]]

Output : 6

Explanation : Initial matrix = [[0,0,0],[0,0,0]]. After applying first increment it becomes [[1,2,1],[0,1,0]].

The final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.

 

Example 2 :

Input : m = 2, n = 2, indices = [[1,1],[0,0]]

Output : 0

Explanation : Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.

 

Constraints :

• 1 <= m, n <= 50
• 1 <= indices.length <= 100
• 0 <= ri < m
• 0 <= ci < n

 

Follow up : Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

---

이 문제를 직역하자면 : " 주어진 m x n 행렬이 모두 0으로 초기화됩니다. 또한 indices라는 2D 배열이 주어지며,

각 indices[i] = [ri, ci]는 행렬에서 수행해야 하는 증분 작업을 나타냅니다.

각 indices[i]에 대해 다음 작업을 수행합니다 :

1. ri 행의 모든 셀을 증가시킵니다.
2. ci 열의 모든 셀을 증가시킵니다.

이 작업을 모두 수행한 후, 행렬에서 홀수 값을 가진 셀의 개수를 반환하세요."

입니다.

 

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] finalMatrix = new int[m*n];

        for (int i = 0; i < indices.length; i++) {
            for (int c = 0; c < n; c++) {
                finalMatrix[n * indices[i][0] + c] += 1;
            }
            for (int r = 0; r < m; r++) {
                finalMatrix[r * n + indices[i][1]] += 1;
            }
        }

        int oddCount = 0;
        for (int x = 0; x < m*n; x++) {
            if (finalMatrix[x] % 2 != 0) {
                oddCount++;
            }
        }

        return oddCount;
    }
}

 

이 코드는 주어진 m x n 행렬에서 각 행과 열에 증분 작업을 수행한 후, 홀수 값을 가진 셀의 개수를 반환하는 문제를 해결합니다. finalMatrix 배열을 사용하여 일차원 배열로 행렬을 표현하고, 각 행과 열의 증분 작업을 수행합니다.

1. 일차원 배열 초기화 (finalMatrix) :
   • m x n 크기의 행렬을 일차원 배열 finalMatrix로 표현합니다.
   • 초기값은 모두 0으로 설정됩니다.
2. 증분 작업 수행 :
   • 주어진 indices 배열을 순회하면서 각 행과 열에 증분 작업을 수행합니다.
   • 각 인덱스 쌍 indices[i]에 대해 :
     • indices[i][0] 행의 모든 셀을 증분 합니다.
     • indices[i][1] 열의 모든 셀을 증분 합니다.
   • 행의 셀을 증분 할 때는 n * indices[i][0] + c로 접근합니다.
   • 열의 셀을 증분할 때는 r * n + indices[i][1]로 접근합니다.
3. 홀수 값 셀의 개수 계산 :
   • finalMatrix 배열을 순회하며 각 셀이 홀수인지 확인합니다.
   • 홀수인 셀의 개수를 oddCount 변수에 저장합니다.
4. 결과 반환 :
   • 홀수 값 셀의 개수를 반환합니다.

• 시간 복잡도 : O(m * n + k * (m + n))
  • 각 인덱스 쌍에 대해 행과 열의 셀을 증분 하는 작업은 O(k * (m + n)) 시간이 소요됩니다. 여기서 k는 indices 배열의 길이입니다.
  • 최종적으로 모든 셀을 검사하는 작업은 O(m * n) 시간이 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(k * (m + n) + m * n)입니다.

• 공간 복잡도 : O(m * n)
  • 행렬을 일차원 배열 finalMatrix로 표현하므로, 배열의 크기는 m * n입니다.
  • 따라서 전체 공간 복잡도는 O(m * n)입니다.

하지만 제 코드는 Follow-up에 미치지 못하였습니다. 하여서, ChatGPT한테 물어본 결과, 이 코드를 줬습니다 : 

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rowCounts = new int[m];
        int[] colCounts = new int[n];

        // indices 배열을 순회하며 행과 열의 증분을 기록
        for (int[] index : indices) {
            rowCounts[index[0]]++;
            colCounts[index[1]]++;
        }

        int oddCount = 0;

        // 행렬의 각 셀을 순회하며 홀수 값 셀의 개수를 계산
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((rowCounts[i] + colCounts[j]) % 2 != 0) {
                    oddCount++;
                }
            }
        }

        return oddCount;
    }
}

 

이 코드 작동 방식은 이렇습니다 :

• 행과 열의 증분 카운트 :
  • rowCounts 배열은 각 행이 얼마나 많이 증가되었는지를 기록합니다.
  • colCounts 배열은 각 열이 얼마나 많이 증가되었는지를 기록합니다.
  • indices 배열을 순회하면서 각각의 행과 열의 증분을 기록합니다.
• 홀수 값 셀의 개수 계산 :
  • 행렬의 각 셀에 대해 해당 셀의 값이 홀수인지 확인합니다.
  • 셀의 값은 rowCounts[i] + colCounts[j]로 계산됩니다.
  • 해당 값이 홀수이면 oddCount를 증가시킵니다.
• 결과 반환 :
  • 모든 셀을 검사한 후 홀수 값 셀의 개수를 반환합니다.

시간 복잡도와 공간 복잡도는 : 

• 증분 횟수 기록 : O(k)
  • indices 배열을 순회하면서 각 행과 열의 증분 횟수를 기록하는 작업은 O(k) 시간이 소요됩니다. 여기서 k는 indices 배열의 길이입니다.
• 홀수 값 셀의 개수 계산 : O(m * n)
  • 행렬의 각 셀을 순회하면서 홀수 값을 가진 셀의 개수를 계산하는 작업은 O(m * n) 시간이 소요됩니다.

따라서 전체 시간 복잡도는 O(k + m * n)입니다.

 

• 행 및 열 증분 카운트 배열 : O(m + n)
  • rowCounts 배열과 colCounts 배열은 각각 m과 n 크기의 공간을 차지합니다.
  • 따라서 전체 공간 복잡도는 O(m + n)입니다.

---

내 코드와 GPT 코드 Runtime 결과