[프로그래머스 lv2] 쿼드압축 후 개수 세기 (queue 풀이)

월간 코드 챌린지 시즌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 입니다.

---

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

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

• 

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

입출력 예 #2

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

  

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

---

나의 풀이

재귀적인 방법도 있을 것이고, 그 외 다양한 풀이가 있겠지만 나는 queue를 사용해 풀이했다.

큐에서 arr를 하나 뽑아서 0 혹은 1로만 이루어진 배열인지 확인 후 0 혹은 1로만 이루어졌다면 answer에 추가를 하고, 그렇지 않다면 arr를 4조각으로 쪼개어 다시 큐에 넣어줬다.

이 과정을 큐가 빌 때까지 반복하면 쿼드 압축 후 0, 1의 개수를 얻을 수 있다.

from collections import deque

def solution(arr):
    answer = [0, 0]
    queue = deque([arr])
    while queue:
        now = queue.popleft()
        if check(now)==0: answer[0]+=1
        elif check(now)==1: answer[1]+=1
        else:
            size = len(now) // 2
            queue.append([now[x][:size] for x in range(size)]) # 2사분면
            queue.append([now[x][size:] for x in range(size)]) # 1사분면
            queue.append([now[x][:size] for x in range(size,size*2)]) # 3사분면
            queue.append([now[x][size:] for x in range(size,size*2)]) # 4사분면
    return answer

def check(arr):
    size = len(arr)
    n = arr[0][0]
    return n if [[n]*size for _ in range(size)] == arr else 2

check 함수에서는 arr의 첫 번째 요소 n을 확인 후 arr와 같은 크기의 n으로만 이루어진 배열을 만들어 비교를 했다.

만약 0으로만 이루어졌다면 0을, 1로만 이루어졌다면 1을, 그렇지 않다면 2를 return하는 함수이다.

 

테스트 결과