[Swift Algorithm] 68936 쿼드압축 후 개수 세기 (월간 코드 챌린지1)

programmers.co.kr/learn/courses/30/lessons/68936

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

풀이방법

 

핵심은 '해당 영역의 요소들이 모두0 혹은 모두1인 경우 하나로 압축 할 수 있다.' 겟죠?!

 

우선그럼 해당 영역을 쪼개야겟죠 

 

예를들어 4칸이있다고하면

행과 열 모두 범위가 0..<4 만큼을 4분할로 하기때문에 반씩 나누겠죠

중간값은 2이고

0..<2 와 2..<4로 나뉘겠네요

 

행이 0..<2 열이 0..<2 -> 좌상단 2x2 사각형

행이 0..<2 열이 2..<4 -> 우상단 2x2 사각형

행이 2..<4 열이 0..<2 -> 좌하단 2x2 사각형

행이 2..<4 열이 2..<4 -> 우하단 2x2 사각형

으로 나눌 수 있겟죠?

 

이렇듯 배열의 한칸 길이가 n인 사각형을 4분할 하는방법은

startRow, startCol, endRow, endCol을 통해서 행과 열의 시작점과 끝점을 알 수 있다면 

중간값인 mid를 구하고

조합을 통해서

좌상단, 우상단, 좌하단, 우하단을

재귀를 통해서 계속 분할 할 수 있어요

 

해당 범위만큼 탐색을통해서 같은 수가 있는지 체크하고

압축을 했다는 플레그를 통해서 중복 계산하지 않도록 막았구요

 

계속 재귀를 해서 끝까지가면 1x1인 사각형 까지 가기때문에 

탐색할 때 계산하도록 했어요

 

// 쿼드 압축 후 개수 세기
private func solutionP68936(_ arr:[[Int]]) -> [Int] {
   var isZip = arr.map { _ in Array(repeating: false, count: arr.count) }
   var zeroCount = 0
   var oneCount = 0
   
   // 해당 범위를 순회 모든 값이 같으면 압축
   func search(row: Range<Int>, col: Range<Int>) -> Bool {
       
       let first = arr[row.first!][col.first!]
       for i in row {
           for j in col {
               if isZip[i][j] {
                   return false
               }
               if first != arr[i][j] {
                   return false
               }
           }
       }
       
       if first == 0 {
           zeroCount += 1
       } else {
           oneCount += 1
       }
       excuteZip(row: row, col: col)
       return true
   }
   
   // 압축 플레그 표시
   func excuteZip(row: Range<Int>, col: Range<Int>) {
       
       if row.count == 1 || col.count == 1 {
           return
       }
       for i in row {
           for j in col {
               isZip[i][j] = true
           }
       }
   }
   
   func areaZip(sr: Int, sc: Int, er: Int, ec: Int) {
       // 현재 자신 탐색
       if search(row: sr..<er, col: sc..<ec) {
           return
       }
       
       let midr = (sr + er) / 2
       let midc = (sc + ec) / 2
       if midr == sr || midc == sc {
           return
       }
      
       let leftTop = (sr..<midr, sc..<midc)
       let rightTop = (sr..<midr, midc..<ec)
       let leftBottom = (midr..<er, sc..<midc)
       let rightBottom = (midr..<er, midc..<ec)
       
       if !search(row: leftTop.0, col: leftTop.1) {
           areaZip(sr: sr, sc: sc, er: midr, ec: midc)
       }
       
       if !search(row: rightTop.0, col: rightTop.1) {
           areaZip(sr: sr, sc: midc, er: midr, ec: ec)
       }
       
       if !search(row: leftBottom.0, col: leftBottom.1) {
           areaZip(sr: midr, sc: sc, er: er, ec: midc)
       }
       
       if !search(row: rightBottom.0, col: rightBottom.1) {
           areaZip(sr: midr, sc: midc, er: er, ec: ec)
       }
   }
  
   areaZip(sr: 0, sc: 0, er: arr.count, ec: arr.count)
   
   print([zeroCount,oneCount])
   return [zeroCount,oneCount]
}