[프로그래머스,kotlin] 쿼드압축 후 개수 세기

 

문제해결 POINT

문제설명의 2,3 번 조건을 통해 이 문제는 분할정복 문제임을 알 수 있다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

분할정복 문제는 아래 3단계를 통해 해결 할 수 있다.

   1. 작은 영역으로 나눈다.

   2. 나누어진 작은 영역을 계산한다

   3. 필요하다면  해결된 답을 모은다. 

 

isUniform 함수:

• 이 함수는 주어진 영역이 모두 동일한 값을 가지는지 확인합니다.
• x와 y는 영역의 시작 좌표, size는 영역의 크기입니다.
• 영역의 모든 값을 검사하여 동일한 값이면 true를, 그렇지 않으면 false를 반환합니다.

 

compress 함수:

• 이 함수는 재귀적으로 배열을 4개의 부분으로 나누고, 각 부분에 대해 압축을 시도합니다.
• x와 y는 현재 영역의 시작 좌표, size는 현재 영역의 크기입니다.
• 현재 영역이 모두 동일한 값을 가지면 결과 배열에 0 또는 1의 개수를 증가시킵니다.
• 그렇지 않으면 4개의 부분으로 나누어 다시 압축을 시도합니다.

 

해결 코드

fun solution(arr: Array<IntArray>): IntArray {
    // 특정 영역이 모두 동일한 값인지 확인하는 함수
    fun isUniform(x: Int, y: Int, size: Int): Boolean {
        val value = arr[x][y]
        for (i in x until x + size) {
            for (j in y until y + size) {
                if (arr[i][j] != value) {
                    return false
                }
            }
        }
        return true
    }

    // 쿼드 트리 분할 및 압축 함수
    fun compress(x: Int, y: Int, size: Int, result: IntArray) {
        if (isUniform(x, y, size)) {
            if (arr[x][y] == 0) {
                result[0]++
            } else {
                result[1]++
            }
        } else {
            compress(x, y, size / 2, result)
            compress(x, y + size / 2, size / 2, result)
            compress(x + size / 2, y, size / 2, result)
            compress(x + size / 2, y + size / 2, size / 2, result)
        }
    }

    val result = intArrayOf(0, 0)
    compress(0, 0, arr.size, result)
    return result
}