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

🔗

풀이

길이가 1이 될 때까지 4등분을 하고 그 값을 리턴하면서 4칸이 일치하는지 여부를 확인했다. 길이가 1이면 해당 칸의 값을 반환하고, 1이 아니면 4개의 칸으로부터 오는 값들을 검사한다. 길이가 1일 때 이미 해당 값의 개수를 카운트 해줬기 때문에 4칸이 동일하다면 3칸의 값을 제외해주어야 한다. 4개의 칸의 값이 동일하지 않다면 아무 값도 반환하지 않아야 하며 자료형을 맞춰서 반환한다.

어차피 일부 어떤 칸에서 4개 칸의 값이 동일하지 않다면 그 칸을 포함하고 있는 더 큰 칸 역시 4개 칸의 값이 모두 동일할 수 없기 때문이라는 점을 생각하면 쉽게 풀리는 것 같다.

def solution(arr):
    answer = [0, 0]
    def square(x1, y1, d):
        if d == 1:
            answer[arr[x1][y1]] += 1
            return {arr[x1][y1]}
        
        d //= 2
        s1 = square(x1, y1, d)
        s2 = square(x1, y1+d, d)
        s3 = square(x1+d, y1, d)
        s4 = square(x1+d, y1+d, d)
        if len(s1) == 1 and s1 == s2 == s3 == s4:
            answer[list(s1)[0]] -= 3
            return s1
        return set()

    square(0,0,len(arr))
    return answer