코딩테스트 연습 - 쿼드압축 후 개수 세기

문제 풀이 아이디어

쿼드 압축의 과정을 보면 이차원 배열을 압축할 수 없으면 해당 배열을 1/4한 이후에 같은 과정을 반복하면서 압축을 하고 있습니다. 그리고 이차원 배열의 크기가 1 x 1가 되어서 더 이상 압축할 수 없다면 압축이 끝납니다.

이는 재귀함수를 통해서 구현할 수 있습니다. 압축이 되는 경우 혹은 배열의 크기가 1 x 1인 경우 리턴을 하고 (탈출 조건) 아닌 경우에는 1/4해서 재귀함수를 실행하면 됩니다.

코드

ArraySlice를 이용한 방식

주어진 arr의 최대 크기는 1024입니다. 따라서 상대적으로 비용이 큰 ArraySlice를 사용해서 이차원 배열을 4등분해도 큰 문제가 없습니다.

func solution(_ arr:[[Int]]) -> [Int] {
    // 주어진 이차원 배열이 압축이 가능한지 알아보는 함수
    func isCompressable(_ arr: [[Int]]) -> Bool {
        // 이차원 배열의 첫 원소
        let num = arr[0][0]
        
        // 이차원 배열의 모든 원소가 첫 원소와 같은지 확인
        for i in 0..<arr.count {
            for j in 0..<arr.count {
                // 다르면 false 리턴
                if arr[i][j] != num { return false }
            }
        }
        
        // 반복문 통과하면 true 리턴
        return true
    }
    
    // arr를 1/4 해주는 함수
        //👉 i와 j는 0 혹은 1
    func slice(_ arr: [[Int]], _ i: Int, _ j: Int) -> [[Int]] {
        let size = arr.count / 2
        var result = [[Int]]()
        // 먼저 행을 1/2하고
        var arr = arr[size * i..<size * (i + 1)]
        for line in arr {
            // 그 행을 각각 1/2해서 1/4인 이차원 배열을 만든다.
            result.append(Array(line[size * j..<size * (j + 1)]))
        }
        return result
    }
    
    // 재귀함수
    func sol(_ arr: [[Int]]) -> [Int] {
        // 결과 저장을 위한 배열
        var result = [0, 0]
        
        // 탈출조건 arr의 크기가 1x1일 때
        if arr.count == 1 {
            let num = arr[0][0]
            result[num] += 1 //👉 결과에 내용물을 더하고 리턴
            return result
        }

        // 압축할 수 있다면
        if isCompressable(arr) {
            let num = arr[0][0]
            result[num] += 1 //👉 결과에 압축한 숫자를 하나 더하고 리턴
            return result
        // 압축할 수 없다면
        } else {
            // 4분의 1해서 각각 재귀함수 실행
            for i in 0..<2 {
                for j in 0..<2 {
                    let sliceResult = sol(slice(arr, i, j))
                    result[0] += sliceResult[0]
                    result[1] += sliceResult[1]
                }
            }
        }

        return result
    }

    return sol(arr)
}

Array의 index를 사용하는 방법

이번에는 ArraySlice를 사용하지 않는 방법으로 구현해보겠습니다. 실행 시간을 비교해보면 ArraySlice를 사용하는 방법보다 훨씬 빠릅니다. 아무리 N이 작아도 ArraySlice를 사용하지 않는 습관을 들이는 것이 좋습니다. 알고리즘도 아니고 언어의 성능 때문에 시간초과를 받으면 억울하니까요ㅎㅎ

isCompress 부분도 조금 수정해보았습니다.

func solution(_ arr:[[Int]]) -> [Int] {
    // 압축이 가능하면 압축한 숫자, 불가능하면 nil을 리턴하는 함수
    func compress(_ row: Int, _ col: Int, _ size: Int) -> Int? {
        // 이차원 배열의 첫 원소
        let num = arr[row][col]

        // 이차원 배열의 모든 원소가 첫 원소와 같은지 확인
        for i in row..<(row + size) {
            for j in col..<(col + size) {
                // 다르면 nil 리턴
                if arr[i][j] != num { return nil }
            }
        }
        // 반복문을 통과하면 압축한 숫자를 리턴
        return num
    }
    
    // 재귀함수
    func sol(_ row: Int, _ col: Int, _ size: Int) -> [Int] {
        // 결과를 저장할 배열
        var result = [0, 0]
        
        // arr의 크기가 1 x 1이면 탈출
        if size == 1 {
            result[arr[row][col]] += 1
            return result
        }
        
        // 압축이 가능하면 결과에 반영하고 리턴
        if let compress = compress(row, col, size) {
            result[compress] += 1
            return result
        // 압축이 불가능한 경우
        } else {
            // 사이즈를 1/2로 줄여서 4조각을 다시 재귀함수 돌리기
            let newSize = size / 2
            for i in 0..<2 {
                for j in 0..<2 {
                    let newRow = row + newSize * i
                    let newCol = col + newSize * j
                    let newResult = sol(newRow, newCol, newSize)
                    result[0] += newResult[0]
                    result[1] += newResult[1]
                }
            }
        }
        
        return result
    }
    
    let size = arr.count
    
    return sol(0, 0, size)
}