Programmers 쿼드압축 후 개수 세기 [Swift]

https://programmers.co.kr/learn/courses/30/lessons/68936?language=swift 

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

 

 

바로 본론으로 들어가서 풀이해보자.

다음과 같은 n x n 정사각형이 있다. 

 

그렇다면 한 변의 길이 n은 arr의 길이가 되겠다. (arr의 첫 번째 요소의 길이로 줘도 된다.)

그런데 이것을 압축하려면 모든 요소를 하나씩 다 돌면서 모든 숫자가 0인지 1인지 판단해야 한다.

전부 다 0이거나 전부 다 1인 경우는 처음부터 끝까지 다 돌면서 확인하면 되겠지만 그렇지 않은 경우가 문제다.

자, 그럼 이제 난관을 헤쳐나갈 풀이를 공개한다.

 

먼저 4 * 4 정사각형이 있다고 하자.

그러면 (0, 0) ~ (3, 3) 까지 다 돌면서 일단 숫자가 다 일치하는지 구한다.

그런데 아래 그림에서 (0, 2) 부분이 최초 값(0,0)과 다르다는 것이 파악됐다. 

 

 

그러면, 이제 사각형을 네 개로 나눠서 다시 이 로직을 반복한다.

네 개로 나누는 방법은 이렇다.

행 정보를 row, 열 정보를 col, 그리고 길이를 n 이라고 했을 때

1사분면: row와 col은 그대로이면서 n만 2로 나누어 row~n/2, col~n/2 이 되도록 한다. (0..<2 0..<2)

2사분면: row는 그대로지만 col은 col + n/2이 되어야 한다. n은 역시 n/2로 나누어준다. (0..<2 2..<4)

3사분면: row는 row + n/2가 되어야 한다. col은 그대로. n은 n/2 (2..<4 0..<2)

4사분면: row는 row + n/2, col도 col + n/2, n은 n/2 (2..<4 2..<4)

 

이제 좀 감이 잡히는가?

정답 코드를 보면서 이해를 완벽하게 해보자.

import Foundation

var zeroCount = 0
var oneCount = 0
    
func recursive(_ arr: [[Int]], _ row: Int, _ col: Int, _ n: Int) {
    var norm = arr[row][col] // 최초값
    
    for i in row..<row + n {
        for j in col..<col + n {
            if norm != arr[i][j] {
                recursive(arr, row, col, n/2) //0..<2 0..<2
                recursive(arr, row, col + n/2, n/2) //0..<2 2..<4
                recursive(arr, row + n/2, col, n/2) //2..<4 0..<2
                recursive(arr, row + n/2, col + n/2, n/2) //2..<4 2..<4
                
                
                return
            }
        }
    }
    if norm == 1 { oneCount += 1 }
    else { zeroCount += 1 }
}

func solution(_ arr:[[Int]]) -> [Int] {
    var n = arr.first!.count
    recursive(arr, 0, 0, n)
    
    return [zeroCount, oneCount]
}