flip And Invert Image

Algorithm
algorithm, leetcode

leetcode 문제링크

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

  • Input: [[1,1,0],[1,0,1],[0,0,0]]
  • Output: [[1,0,0],[0,1,0],[1,1,1]]
  • Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
  • Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

  • Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
  • Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
  • Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
  • Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j] <= 1

나의 풀이

문제를 요약하면 0과 1로만 이루어진 2차원 배열을 수평으로 한번 뒤집고, 0은 1로 1은 0으로 치환되면 된다.
이미지 파일을 뒤집는 방법이 이런식으로 이루어지나 보다.

1
2
3
4
5
6
7
8
9
10
11
// 72 ms
var flipAndInvertImage = function(A) {
    const arr = A;
    for (let i = 0, l = arr.length, n = arr[0].length; i < l; i++) {
        arr[i].reverse();
        for (let j = 0; j < n; j++) {
            arr[i][j] = arr[i][j] === 1 ? 0 : 1; 
        }
    }
    return arr;
};

2차원 배열이니 for문을 2번 썼다.
for문을 두번 쓰는 다음과 같은 경우에는 적절한 것 같은데, reverse가 원본 배열을 바꾸는 메소드이고 arr[i][j]에 값을 대입하는 부분 역시 원본 배열에 변화를 주기 때문에 만약에 원본 배열에 영향을 주고 싶지 않다면 깊은복사를 할 수 있도록 고려해야 될 것 같다.

그렇다면 다음과 같은 방법을 사용하면 인자로 넘겨지는 원본 배열에 변형 없이 새로운 배열을 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
// 68 ms
var flipAndInvertImage = function(A) {
    const newArr = [];
    for (let i = 0, l = A.length, n = A[0].length; i < l; i++) {
        const newRow = A[i].concat().reverse();
        for (let j = 0; j < n; j++) {
            newRow[j] = newRow[j] === 1 ? 0 : 1; 
        }
        newArr.push(newRow);
    }
    return newArr;
};

또 다른 방법으로 for of 문을 쓰면서 map 메소드를 사용하는 방법을 써봤다.

1
2
3
4
5
6
7
8
9
// 64 ms
var flipAndInvertImage = function(A) {
    const newArr = [];
    for (const i of A) {
        const newRow = i.concat().reverse().map(item => item === 1 ? 0 : 1)
        newArr.push(newRow);
    }
    return newArr;
};

다른 사람 풀이

map을 두번 써서 풀었다. 그런데 이 풀이도 만약에 원본 배열을 바꾸고 싶지 않다면 reverse() 메소드 이전에 복사하는 부분이 없기 때문에 변형이 생긴다.

1
2
3
var flipAndInvertImage = function(A) {
    return A.map(row => row.reverse().map(num => num ? 0 : 1))
};

Share Comments