Algorithm / 쿼드압축 후 개수 세기

문제

프로그래머스 / 쿼드 압축 후 개수 세기

1) 문제 풀이

• 현재 영역 S가 모두 같은 값인지 확인
  • 만약 모두 같다면 그 값이 0인지 1인지 확인
  • 다르다면 4등분하여 재귀 호출
• 마지막에 전체 0 개수, 1 개수를 합쳐서 리턴

func solution(_ arr:[[Int]]) -> [Int] {
    var zeroCount = 0
    var oneCount = 0
    
    func divide(_ x: Int, _ y: Int, _ size: Int) {
        let first = arr[x][y]
        var isSame = true
        
        for i in x..<x+size {
            for j in y..<y+size {
                if arr[i][j] != first {
                    isSame = false
                    break
                }
            }
            if !isSame { break }
        }
        
        if isSame {
            if first == 0 {
                zeroCount += 1
            } else {
                oneCount += 1
            }
        } else {
            let half = size / 2
            divide(x, y, half)               // 왼쪽 위
            divide(x, y + half, half)        // 오른쪽 위
            divide(x + half, y, half)        // 왼쪽 아래
            divide(x + half, y + half, half) // 오른쪽 아래
        }
    }
    
    divide(0, 0, arr.count)
    return [zeroCount, oneCount]
}

결과