Skip to content

Files

Latest commit

 

History

History
45 lines (34 loc) · 2.03 KB

풀이_쿼드압축후개수세기.md

File metadata and controls

45 lines (34 loc) · 2.03 KB

🧚🏻‍♀️ 프로그래머스 쿼드압축 후 개수 세기

  • Date : 2020.10.20(화)
  • Time : 60분

문제

  • 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

    • 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
    • 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
    • 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
  • arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

코드 풀이

    left_up = check(y, x, n // 2)
    right_up = check(y, x + n // 2, n // 2)
    left_down = check(y + n // 2, x, n // 2)
    right_down = check(y + n // 2, x + n // 2, n // 2)

: 먼저 정수 배열이 1칸이 아니라면 4개의 균일한 정사각형 영역으로 나눠준다.

    if n == 1:
        return [0, 1] if arr[y][x] == 1 else [1, 0]

: 이 와중에 1칸으로 다 나눠졌다면 칸의 값이 1이면 [0,1], 칸의 값이 0이면 [1,0]을 준다. [0,1]의 뜻은 0이 0개 , 1은 1개 라는 뜻이다~

    if left_up == right_up == left_down == right_down == [0,
                                                              1] or left_up == right_up == left_down == right_down == [
            1, 0]:
        return left_up
    else:
        return list(map(sum, zip(left_up, right_up, right_down, left_down)))

: 그래서 각 칸을 봤는데 모두 같은 숫자이면 크게 한 숫자로 합칠 수 있다. 하지만 그것이 아니라면 각자의 값을 합쳐준다.