손가락놀이터

문제 리뷰

처음 문제를 보고 단순히 완전탐색을 활용하여 풀려고 했으나 안된다는 것을 알고 방향을 바꿨습니다. DP를 이용하는 것이 가장 좋아보여서 적용 시켜서 풀었습니다.

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

가 있다면 가장 큰 정사각형은

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

def solution(board):

    if len(board[0]) < 2:
        if [1] in board:
            return 1
        else:
            return 0
    for i in range(1, len(board)):
        for j in range(1, len(board[0])):
            if board[i][j] >= 1:                
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1

    return max([num for row in board for num in row]) ** 2

해당 문제는 Jinomad님의 문제 풀이를 보고 작성한 문서입니다.

문제를 처음 보고 재귀로 해결해야겠다는 생각이 들었지만 어떻게 배열을 Divide할지 고민을 했습니다. 계속해서 배열을 고민했고 스스로 정한 시간인 90분을 넘어서 구글링을 통해 해답을 인지하고 해결했습니다.

Jinomad님의 해결 방식을 보았고 배열이 1과 0으로 구분된다는 점, 단순히 갯수를 센다는 점을 이용하여 count를 생각한다는 것에 놀랐습니다. count하는 것과 관련된 문제를 풀기는 했지만 잊은 것 같아 작성하여 잊지 않으려 합니다 :)

문제 설명

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

입출력 예시

from itertools import chain

def solution(arr):
    # 재귀함수 구현
    def quad(arr):

        arr_len = len(arr) # arr의 길이
        unit = arr_len // 2 # arr을 나누기 위해 사용할 단위
        arr_sum = sum(chain(*arr)) # arr의 모든 요소를 합한 것.
        # chain은 다배열을 1차원 배열로 합쳐주는 함수

        if arr_len == 1: # 마지막까지 압축되지 않았을 경우
            return [arr[0][0]]
        elif arr_sum == arr_len * arr_len: # 모든 요소가 1일 경우
            return [1]
        elif arr_sum == 0: # 모든 요소가 0일 경우
            return [0]

        # arr을 4개의 배열로 나눔

        arr1 = [ar[0:unit] for ar in arr[0:unit]]
        arr2 = [ar[unit:] for ar in arr[0:unit]]
        arr3 = [ar[0:unit] for ar in arr[unit:]]
        arr4 = [ar[unit:] for ar in arr[unit:]]

        result = quad(arr1) + quad(arr2) + quad(arr3) + quad(arr4)  # 나눈 4개의 배열을 다시 확인
        
        return result
    
    # 함수 대입
    answer = quad(arr)
    return [answer.count(0), answer.count(1)]