[Leet Code] 832. Flipping an Image

문제 원본: https://leetcode.com/problems/flipping-an-image/

문제

n x n의 이진 행렬 image가 주어질 때, 이미지를 수평으로 뒤집고 반전시켜 반환하라.

이미지를 수평으로 뒤집는 것은 이미지의 각 행이 뒤집히는 것이다.

• 예시로 [1, 1, 0]을 수평으로 뒤집는 것의 결과는 [0, 1, 1]이다.

이미지를 반전시키는 것은 각각의 0이 1로 바뀌고, 각 1이 0으로 바뀌는 것이다.

• 예시로 [0, 1, 1]을 반전시키면 [1, 0, 0]이 된다.

Example 1:

Input: image = [[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: image = [[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]]

Constraints:

• n == image.length
• n == image[i].length
• 1 <= n <= 20
• images[i][j]는 0이나 1중에 하나이다.

접근 방법

문제에서 나는 기능을 두 가지로 분류했다. 하나는 뒤집기이고, 나머지로는 반전이었다.
뒤집는 거야 swap 알고리즘 써서 반절만 뒤집으면 그만이라고 생각했다.
조금 생각을 한 부분이 반전 연산이었다. 반전 연산을 그냥 간단하게 if문을 돌게 하자니, 20 * 20의 이미지면 총 400개의 요소를 전부 if문을 거쳐야 한다. 그건 싫어서 조건 없이 실행할 방법을 생각하다 반전 연산자인 xor 연산을 이용하기로 했다. 요소는 어차피 0 아니면 1이니까 비트 연산을 수행해도 상관 없다.
만약 요소가 1이라면 1 ^ 1 = 0, 요소가 0이라면 0 ^ 1 = 1로 바뀔 것이다. 그래서 모든 요소를 1과 xor 연산하였다.

풀이

Java

class Solution {
    public int[][] flipImage(int[][] image, int length) {
        for (int row = 0; row < length; row++) {
            for (int col = 0; col < length / 2; col++) {
                int temp = image[row][col];
                image[row][col] = image[row][length - col - 1];
                image[row][length - col - 1] = temp;
            }
        }
        return image;
    }
    
    public int[][] invertImage(int[][] image, int length) {
        for (int row = 0; row < length; row++) {
            for (int col = 0; col < length; col++) {
                image[row][col] ^= 1;
            }
        }
        return image;
    }
    
    public int[][] flipAndInvertImage(int[][] image) {
        int length = image.length;
        
        image = flipImage(image, length);
        image = invertImage(image, length);
        
        return image;
    }
}

• Runtime: 1ms
• Memory: 43.6MB

다른 유저들 보면 flipImage()와 invertImage()를 한 번에 수행하던데, 나랑 성능 면에서는 별 차이가 없었다. swap을 하면서 바로 비트 연산을 하는 방식이었다.

Python

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for i in range(len(image)):
            image[i].reverse()
            for j in range(len(image[i])):
                image[i][j] ^= 1
        return image

• Runtime: 57ms
• Memory: 13.8MB

참고로 파이썬에는 배열을 바로 뒤집을 수 있는 reverse()가 있어서 그걸 활용했다. 자바에도 있기는 한데, 쓰려면 List 형으로 변환했다가 다시 int[]로 변환해야 해서 쓰지 않았다.