n×m 크기의 행렬이 있다고 가정해 보겠습니다. 행렬의 모든 요소는 처음에 0으로 초기화되어 있으며, indices[i] = [ri, ci] 형태의 인덱스 목록이 주어집니다. 각 [ri, ci] 쌍에 대해 ri번째 행과 ci번째 열에 해당하는 모든 셀의 값을 1씩 증가시켜야 합니다. 모든 연산을 적용한 뒤, 행렬에서 홀수 값을 가진 셀의 개수를 구하는 것이 이 문제의 목표입니다.
문제 해결 접근 방법
다음 단계를 순서대로 따라가면 문제를 해결할 수 있습니다.
- 카운터 변수 odd를 0으로 초기화하고, x는 주어진 인덱스 쌍의 개수로 설정합니다.
- n×m 크기의 행렬 mat을 생성합니다.
- i를 0부터 x-1까지 반복하면서 r = input[i][0], c = input[i][1]로 설정합니다.
- j를 0부터 m-1까지 반복하며 mat[r][j]의 값을 1씩 증가시킵니다.
- 이어서 j를 0부터 n-1까지 반복하며 mat[j][c]의 값을 1씩 증가시킵니다.
- 모든 셀을 순회하면서 mat[i][j]와 1을 비트 AND(&) 연산한 결과를 odd에 더합니다. 비트 AND 연산은 값이 홀수일 때 1을 반환하므로 홀수 셀의 개수를 정확히 셀 수 있습니다.
- 최종적으로 odd를 반환합니다.
예제 코드
아래 C++ 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int oddCells(int n, int m, vector<vector<int>>& in) {
int odd = 0;
int x = in.size();
vector < vector <int> > mat(n, vector <int>(m));
for(int i = 0; i < x ;i++){
int r = in[i][0];
int c = in[i][1];
for(int j = 0; j < m; j++){
mat[r][j]++;
}
for(int j = 0; j < n; j++){
mat[j][c]++;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)odd += mat[i][j] & 1;
}
return odd;
}
};
main(){
Solution ob;
vector<vector<int>> c = {{0,1},{1,1}};
cout << ob.oddCells(2,3,c);
}입력
2
3
{{0,1},{1,1}}출력
6
동작 과정 살펴보기
위 예제에서 행렬은 2×3 크기이며, 인덱스 쌍은 {0,1}과 {1,1} 두 개입니다. 먼저 {0,1}을 처리하면 0번째 행 전체와 1번째 열 전체가 1씩 증가하여 행렬은 다음과 같이 됩니다.
1 2 1 0 1 0
이어서 {1,1}을 처리하면 1번째 행 전체와 1번째 열 전체가 다시 1씩 증가합니다.
1 3 1 1 3 1
최종적으로 여섯 개 셀 모두 값이 홀수이므로 정답은 6입니다.
복잡도 분석
- 시간 복잡도: 업데이트 단계는 O(k × (n + m))이며, 여기서 k는 인덱스 쌍의 개수입니다. 마지막 카운팅 단계는 O(n × m)입니다.
- 공간 복잡도: 행렬 전체를 저장해야 하므로 O(n × m)입니다.
더 나은 최적화 방법
실제 행렬을 만들지 않고도 문제를 해결할 수 있습니다. 각 행과 열이 몇 번 증가했는지만 기록하면, 셀 (i, j)의 최종 값은 row[i] + col[j]가 됩니다. 이때 홀수 셀의 개수는 다음과 같이 계산할 수 있습니다.
(홀수 값을 가진 행의 개수 × 짝수 값을 가진 열의 개수) + (짝수 값을 가진 행의 개수 × 홀수 값을 가진 열의 개수)
이 방식을 사용하면 시간 복잡도를 O(k + n + m)으로, 공간 복잡도를 O(n + m)으로 줄일 수 있어 행렬 크기가 클 때 훨씬 효율적입니다.