[Algorithm] Programmers : 쿼드압축 후 개수 세기 by Python

[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/68936

※ 2n(x) → 2의 n승(o)
<sup>태그를 이용하여 2의 n승을 표현하였는데 출력에서는 윗첨자가 적용이 안됐다.. 에디터와 미리보기에서는 적용이 되었는데...😂

📌문제 설명

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 입니다.

입출력 예

입출력 예 설명
입출력 예 #1

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

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

입출력 예 #2

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

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

💡 문제 풀이

크기가 2n x 2n인 arr을 쿼드압축(1/4 크기로 분할) 시키면 되는 문제다.

가장 큰 범위부터 압축시키는 것이 배열(arr)에 최종적으로 남는 0, 1의 개수를 최소화시키는 것이다.

따라서, 문제예시 그대로 가장 큰 범위 2n x 2n 크기부터 순차적으로 분할하여 탐색하였다.

step 1)
n : 쿼드압축 진행시 2차원 배열의 길이
num_one : 최종적으로 남는 1의 개수
num_zero : 최종적으로 남는 0의 개수

쿼드압축을 할 수 있는 최소 2차원 배열은 1x1이기 때문에 n이 1이 될때까지 압축을 진행한다.

step 2)
쿼드 압축을 진행하는 2차원 배열의 행, 열 좌표를 얻기 위해서 범위를 다음과 같이 정했다.
range(0, len(arr), n) → 0부터 arr 길이(2n)까지 n 단위(step)로 증가한다.

ex) 8 x 8 크기의 arr이 있다고 하면

쿼드 압축 진행 전은 8 x 8 하나로 arr[:8][:8] 이지만
다음 압축은 arr[:4][:4], arr[:4][:4], arr[4:][:4], arr[4:][4:]로 나눌 수 있다.

step 3)
step 2)에서 행(i), 열(j)의 기준이 되는 좌표와 n을 calculate 함수로 넘기면 압축가능여부에 따라 압축을 진행한다.

calculate 함수 : 쿼드 형태로 나눈 배열의 압축가능여부에 따라 쿼드압축을 진행하는 함수
total : 쿼드 압축이 가능한지 판별하기 위한 변수

주어진 배열의 모든 원소를 total 변수에 더한다.

• if : total 값이 n2과 같다면(즉, 모든 원소가 1이면) 모든 원소에 1/n2값 부여
• elif : total 값이 0이라면(즉, 모든 원소가 0이면) 모든원소에 -1값을 넣고 arr[r][c]값에만 0을 둔다(압축 진행을 표시하기 위함)
• else : 위 두 조건을 만족하지않으면 압축이 불가능하므로 arr을 return

위처럼 조건문을 만든 이유는 다음과 같다.

쿼드 압축을 진행하면 결국 1의 개수는 1개가 된다.
이점을 착안하여 압축 진행시 모든 값을 1/n2으로 지정하였다.
→ arr의 모든 원소를 합하면 1이되기 때문이다.

하지만 0의 경우는 0/n2으로 지정해도 모든 원소가 똑같이 0이되므로 의미가 없어진다.
따라서 0과 1밖에 없는 arr에 -1이라는 임의의 수를 줬다.(나중에 빼준만큼 더해주면 된다.)
그리고 압축이 진행된 부분임을 나타내기 위해서 배열의 원소중 arr[r][c]값에만 0을 주었다.
→ 압축된 결과 0의 개수가 하나임을 알리기 위해서다.

step 4)
쿼드압축을 모두 마친 arr을 탐색하면서 모든 원소의 값을 더했다.

1의 개수는 모든 원소의 값 + (-1)의 개수를 더해주면 된다.
0의 개수는 0의 개수를 구하면 된다.

코드는 아래와 같다.

def calculate(i, j, n, arr):
    total = 0
    for r in range(i, i+n):
        total += sum(arr[r][j:j+n])
    if total == n**2:
        for r in range(i, i+n):
            for c in range(j, j+n):
                arr[r][c] = 1/(n**2)
        return arr
    elif total == 0:
        for r in range(i, i+n):
            for c in range(j, j+n):
                arr[r][c] = -1
        arr[r][c] = 0
        return arr
    else:
        return arr

def solution(arr):
    n = len(arr)
    num_one = 0
    num_zero = 0
    while n != 1:
        for i in range(0, len(arr), n):
            for j in range(0, len(arr), n):
                arr = calculate(i, j, n, arr)
        n //= 2
    for i in arr:
        num_one += sum(i) + i.count(-1)
        num_zero += i.count(0)
    return num_zero, int(num_one)