[ 프로그래머스 - Kotlin ] 쿼드압축 후 개수 세기 ( 코틀린 )

( 월간 코드 챌린지 시즌1 / 쿼드압축 후 개수 세기 )

[문제]

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

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

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

입출력 예시

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

---

[코드]

class Solution {
    private lateinit var map:Array<IntArray>
    fun solution(arr: Array<IntArray>): IntArray {
        map = arr
        // 길이가 2인 정수 배열을 초기화 하면서 dfs에 넘겨줌
        return IntArray(2).apply{ dfs(map.size, 0, 0, this) }
    }
    // n : 얼마난 크기를 확인할지, x : 시작 x좌표, y :시작 y좌표, answer : 정답
    fun dfs(n:Int, x:Int, y:Int, answer:IntArray){
        // 만일 크기가 제일 작은 1에 도달할 경우
        if(n == 1){
            // 해당하는 숫자 0또는 1의 값을 증가 후 dfs종료
            answer[map[y][x]]++
            return
        }
        // 만일 현재 크기의 사각형 안에 숫자가 모두 같을 경우 dfs 종료
        if(isSame(n,x,y,answer)) return
        // 4개의 면에 대하여 1/2크기로 나누어 dfs다시 진행
        dfs(n/2, x, y, answer)
        dfs(n/2, x, y + n / 2, answer)
        dfs(n/2, x + n / 2, y, answer)
        dfs(n/2, x + n / 2, y + n / 2, answer)
    }
    // n : 얼마난 크기를 확인할지, x : 시작 x좌표, y :시작 y좌표, answer : 정답
    fun isSame(n:Int, x:Int, y:Int, answer:IntArray):Boolean{
        // 모두 같은 숫자인지 비교할 값
        val first = map[y][x]
        for(i in y until y + n){
            for(j in x until x + n){
                // 중간에 다른 숫자가 나오면 false return
                if(first != map[i][j]) return false
            }
        }
        // 모두 같은 숫자일 경우 해당 숫자 증가 후 true return
        answer[first]++
        return true
    }
}

문제 링크

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

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄