프로그래머스 Lv. 2 Swift 알고리즘 - 쿼드압축 후 개수 세기

오늘도 재귀와 싸웠다...

결국 스스로 풀지 못했는데...

앞 부분까진 전부 이해하고 recursive를 걸어야하는 상황에서 어떻게 진행할지 감이 안잡혀서 다른 분들의 코드를 참고했다.

(참고: https://42kchoi.tistory.com/m/374)

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 먼저 배열의 원소들을 4등분해야하기 때문에 미리 4등분된 배열을 만들어두고
2. 그 안에 4사분면의 위치에 맞게 원소들을 넣어주고
3. 그 안의 원소들이 전부 0이거나 1이면 원소들을 모두 지우고 0 or 1의 원소만 넣어주었다.
4. 이 후 하나로 합쳐지지 않은 배열을 다시 4등분으로 조각하여 Recursive를 걸어야하는데 이 부분에서 걸렸다...
5. 다른 분들의 코드를 참고해보니 좀 이해가 갔다.
6. 재귀를 또 4등분으로 아예 나눠서 걸어버려야하는구나..!
7. 그리고 다시 배열을 반환하여 그 배열을 무는 구조가 아닌 끝까지 도달했을 때 값에 영향을 미치는 구조로 Recursive를 설계하는 것이 훨씬 나았겠구나를 깨달았다.

 

 

* 시도하던 코드

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
    var arr1: [[Int]] = [[], [], [], []]

    for i in 0..<arr.count {
        var temp1: [Int] = []
        var temp2: [Int] = []

        if i < arr.count/2 {
            for j in 0..<arr.count/2 {
                temp1.append(arr[i][j])
            }

            for j in arr.count/2..<arr.count {
                temp2.append(arr[i][j])
            }

            arr1[0] += temp1
            arr1[1] += temp2
            
        } else {
            for j in 0..<arr.count/2 {
                temp1.append(arr[i][j])
            }

            for j in arr.count/2..<arr.count {
                temp2.append(arr[i][j])
            }

            arr1[2] += temp1
            arr1[3] += temp2
        }
    }

    for i in 0..<arr1.count {
        if arr1[i].reduce(0, +) == 0 {
            arr1[i] = [0]
        } else if arr1[i].reduce(0, +) == arr.count * 2 {
            arr1[i] = [1]
        } else {

        }
    }
    return []
}

 

 

* 참고 후 코드

import Foundation

var zeroCount = 0
var oneCount = 0
    
func recursive(_ arr: [[Int]], _ row: Int, _ col: Int, _ n: Int) {
    let 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)
                recursive(arr, row, col + n/2, n/2)
                recursive(arr, row + n/2, col, n/2)
                recursive(arr, row + n/2, col + n/2, n/2)
                
                return
            }
        }
    }
    if norm == 1 { oneCount += 1 }
    else { zeroCount += 1 }
}

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

 

 

정리(Today I Learned)

1. 여전히 재귀는 어렵다 ㅠㅠ