[Swift] 프로그래머스 LV2. 쿼드 압축 후 개수 세기

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

 

✅ 문제를 보자마자 재귀로 해야한다고 생각이 들었음.

예전에 학교 수업에서 자료구조 알고리즘 시간에 divide and conquer로 문제를 풀었던 기억이 있는데, 그래서 이를 활용함.

근데 그때는 작은 문제에서 큰 문제로 갔었고, 이번에는 큰 문제에서 작은 문제로 내려가야 했음.

 

 

✅ 코드

// https://programmers.co.kr/learn/courses/30/lessons/68936
import Foundation

struct p68936 {
    static func run() {
        print(p68936.solution([[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]])) // [4,9]
    }
    
    static var zeroCount = 0
    static var oneCount = 0
    
    static func solution(_ arr:[[Int]]) -> [Int] {
        // 재귀 쓰면 금방 풀겠다! -> divide and conquer 해야한다.
        
        reculsive(arr: arr, row: 0, col: 0, n: arr.count)
        return [zeroCount, oneCount]
    }
    
    static func reculsive(arr: [[Int]], row: Int, col: Int, n: Int) {
        let point = arr[row][col] // 시작하는 지점
        
        for i in row..<row + n {
            for j in col..<col + n {
                if point != arr[i][j] {
                    reculsive(arr: arr, row: row, col: col, n: n/2)
                    reculsive(arr: arr, row: row, col: col + n/2, n: n/2)
                    reculsive(arr: arr, row: row + n/2, col: col, n: n/2)
                    reculsive(arr: arr, row: row + n/2, col: col + n/2, n: n/2)
                    
                    return
                }
            }
        }
        
        // 하나의 영역으로 묶였을 경우 or 끝까지 묶이지 않아 n이 1인 경우
        if point == 1 { oneCount += 1 }
        else { zeroCount += 1}
    }
}