문제 링크: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
문제 설명
m x n크기의 이차원 이진수 배열이 주어진 상황에서, 아무 열 (column) 이나 선택해서 그 열의 원소들을 플립할 수 있다. 플립을 여러 번 한 후에 모든 원소가 같은 숫자인 행 (row) 의 최대 갯수를 구하라.
입/출력 예시
1
2
3
Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.
1
2
3
Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.
1
2
3
Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function maxEqualRowsAfterFlips(matrix: number[][]): number {
function arrayEquals(arr1: number[], arr2: number[]) {
return !(arr1 > arr2 || arr1 < arr2);
}
const m = matrix.length;
const n = matrix[0].length;
let counter: { [k: string]: number } = {};
for (let i = 0; i < m; i++) {
let flippedCurrentRow = '';
for (let j = 0; j < n; j++) {
flippedCurrentRow += 1 - matrix[i][j];
}
const currentRow = matrix[i].join('');
counter[currentRow] ??= 0;
counter[flippedCurrentRow] ??= 0;
counter[currentRow] += 1;
counter[flippedCurrentRow] += 1;
}
return Math.max(...Object.values(counter));
};
이 문제를 풀기 위한 아이디어를 생각하는 과정을 설명해 보겠다.
우선, 특정 열을 플립하여 최종적으로 특정 행이 모든 원소가 같으려고 하면, 그 행들은 서로 완전히 같거나 혹은 원소들이 모두 플립된 행과 같아야 한다. 이게 무슨 말이냐 하면, 예를 들어서 수많은 행 중 2개의 행이 아래와 같다고 가정하자.
1
2
3
4
5
...
[0,0,1,0,0]
...
[1,1,0,1,1]
...
이 경우에는 다른 행은 우선 넘어가고, 이 2개의 행은 어떻게든 모든 원소가 같은 행으로 만들 수 있다. 왜냐하면, 세 번째 열을 플립하면 되기 때문이다.
즉, 전체 행을 뒤져보면서, 서로 완전히 같거나 혹은 플립된 형태로 같은 행들의 갯수가 정답이 된다.
자, 이제 각 행을 서로 비교하는 방식으로 구현할 수 있을 텐데, 이렇게 하면 O(m^2) 의 시간 복잡도를 가지게 된다. 좀 더 시간 복잡도를 줄일 수는 없을까?
각 행을 서로 비교하는 것보다는, 특정 행이 등장했을 때, 그 행의 갯수를 +1 씩 하는 카운터 해시를 만들면 좋을 것이다. 즉, 각 행을 1번씩 순회하면서, 그 행 자체와 그 행을 플립한 행을 카운터값에 +1 하면서 순회하게 된다면, O(m) 의 시간 복잡도로도 문제를 해결할 수 있다.
위 설명을 토대로 코드를 좀 더 설명해보자면, counter 라는 변수를 만들었고, 이 변수는 행을 문자열화한 것을 key 로, 그 행이 등장한 횟수를 value 로 갖는 해시 맵 같은 역할을 한다.
예시 입출력 중, matrix = [[0,0,0],[0,0,1],[1,1,0]] 케이스에서 반복문을 돌리고 나면, counter 변수는 아래와 같아진다.
1
2
3
4
count = {'000': 1, '111': 1, '001': 2, '110': 2}
// 첫 번째 행 000 -> 000 과 111 에 대해서 +1
// 두 번째 행 001 -> 001 과 110 에 대해서 +1
// 세 번째 행 110 -> 110 과 001 에 대해서 +1
위와 같은 counter 변수에서 값들 중 최대값을 찾으면 된다. 이 값이 열들을 플립했을 때 완전히 같거나 플립한 형태로 같은 최대 행의 갯수가 된다.
결과
문제를 푼 것만 해도 기분이 좋지만,
시간복잡도 와 공간 복잡도 두 관점 모두 에서 전체 submission 중 최고로 좋은 점수를 받았다!
가끔 둘 중 하나에 대해서 100% 를 달성한 경우는 있었지만, 둘 다 100% 를 달성한 경우는 처음이다. 별거 아니지만 뭔가 뿌듯하고 기쁘다. 다른 문제를 풀 때도 이런 식으로 100% 에 가까운 숫자를 달성할 수 있게 되면 좋겠다.