[프로그래머스/Swift] 68936번 - 쿼드압축 후 개수 세기

🔗 문제 링크

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

💡 구현 아이디어

1. 스택에 전체 범위가 초기로 들어가있음
2. 스택이 비어있지 않으면 값(범위)을 하나 pop
3. 범위 내의 원소가 전부 같은 값인지 확인
4. 같은 값이면 가장 좌하단의 값이 0인지 1인지 판단 후 반영
5. 다른 값이면 4등분해서 스택에 넣음
6. 스택이 비어있지 않으면 2번부터 다시 실행
7. 스택이 비었다면 결과 출력

💻 코드

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
  var result: [Int] = [0, 0]
  var stack: [(Int, Int, Int, Int)] = [(0, 0, arr.count, arr.count)]
  while !stack.isEmpty {
    let pos = stack.removeLast()
    var flag: Bool = true
    for y in pos.1..<pos.3 {
      for x in pos.0..<pos.2 {
        if arr[y][x] != arr[pos.1][pos.0] {
          flag = false
          break
        }
      }
      if !flag { break }
    }
    if flag {
      result[arr[pos.1][pos.0]] += 1
    }else {
      stack.append((pos.0, pos.1, (pos.2+pos.0)/2, (pos.3+pos.1)/2))
      stack.append(((pos.2+pos.0)/2, pos.1, pos.2, (pos.3+pos.1)/2))
      stack.append(((pos.2+pos.0)/2, (pos.3+pos.1)/2, pos.2, pos.3))
      stack.append((pos.0, (pos.3+pos.1)/2, (pos.2+pos.0)/2, pos.3))
    }
  }
  return result
}

❌ 틀린 이유 및 틀린 부분

(x1, y1)~(x2, y2)를 판단해서 4등분으로 나눠야하면 (x1, y1)~((x2+x1) / 2, (y2+y1) / 2) 로 해야하는데 (x2 / 2, y2 / 2)로 계산해서 틀림

⏳ 시간 복잡도

O(2^n) 이지만 행의 개수가 최대 1024개로 1024 * 1024의 입력을 계산할 경우 2^20 * 10 번의 연산횟수가 나온다 대략 천만번의 실행횟수를 가짐

📌 풀이 또는 기억할 정보