[PCCE 기출문제] 10번 / 공원 - Pyton, 누적합(Prefix Sum)

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/340198

프로그래머스

 

코드 & 풀이

 

def solution(mats, park):
    n, m = len(park), len(park[0])
    grid = [[1 if cell == "-1" else 0 for cell in row] for row in park]
    
    prefix_sum = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            prefix_sum[i][j] = (
                grid[i-1][j-1]
                + prefix_sum[i-1][j] 
                + prefix_sum[i][j-1] 
                - prefix_sum[i-1][j-1]
            )
            
    def is_empty(x, y, size):
        x2, y2 = x + size, y + size
        if x2 > n or y2 > m:
            return False
        area_sum = (
            prefix_sum[x2][y2]
            - prefix_sum[x][y2]
            - prefix_sum[x2][y]
            + prefix_sum[x][y]
        )
        return area_sum == size ** 2
    
    mats.sort(reverse = True)
    for mat in mats:
        for i in range(n):
            for j in range(m):
                if is_empty(i, j, mat):
                    return mat
        
    return -1

 

1. 누적합 방식으로 풀이

 

전형적인 누적합 풀이입니다.

 

prefix_map[i][j] = 현재 셀 값 + 위쪽 영역 + 왼쪽 영역 - 중복된 영역입니다.

 

예시를 들자면

 

돗자리를 놓을 수 있는 장소를 체크한 리스트를 grid라 할 때

 

 

i = 4, y = 4까지의 누적합을 구한다면

 

 

왜 8이 나올까요?

 

prefix_map[4][4]의 값은

 

(1, 1)부터 (4, 4)까지의 부분합입니다.

 

prefix_map[3][4] 와 prefix_map[4][3] 또한

 

(1,1)부터 그 위치까지의 부분합입니다.

 

그렇기에 두가지 값을 더하면 중복된 범위가 나오기에

 

prefix_map[3][3] 값을 한 번 빼주는 겁니다.

 

grid의 인덱스가 i-1, j-1인 이유는

 

prefix_map은 1-based 방식이고

 

grid는 0-based 방식이기 때문입니다.

 

위의 과정으로

 

prefix_map[i][j] = grid[i-1][j-1] + prefix_map[i-1][j] + prefix_map[i][j-1]  - prefix_map[i-1][j-1]

 

= 1 + 6 + 6 - 5

 

= 8 이 됩니다.

 

위의 과정을 완료한 후

 

돗자리 크기가 들어있는 mats를 내림차순으로 정렬 후

 

해당 사이즈를 놓을 수 있는지 확인하면 끝납니다.

 

정렬하는 이유는

 

돗자리를 깔 수 있다 == 최대 사이즈로 하여

 

이후의 돗자리를 깔 수 있는지 확인하지 않기 위해서입니다.

 

 

def solution(mats, park):
    answer = -1
    def check_mat(x, y, mat):        
        if x + mat > len(park) or y + mat > len(park[0]):
            return False
        if all(park[x + i][y + j] == "-1" for j in range(mat) for i in range(mat)):
            return True
        
        return False
        # for i in range(mat):
        #     for j in range(mat):
        #         if park[x + i][y + j] != "-1":
        #             return False
        # return True
    
    mats.sort(reverse = True)
    for mat in mats:        
        for i in range(len(park)):
            for j in range(len(park)):
                if check_mat(i, j, mat):
                    return mat
        
    return -1

 

2. 일일이 돗자리 깔아보기

 

이 방법은 그냥 다 확인하는 겁니다.

 

처음에 우선 돗자리를 펼 수 있는지를 인덱스 범위로 검사합니다.

 

이후에는 mat의 범위만큼이 "-1"인지 확인합니다.

 

단순합니다.

 

속도를 비교했을 때 오히려 빠를때도 있지만

 

주어지는 공원의 크기가 커지면 커질수록 누적합이 유리합니다.

 

 

 

다음에 또 봐요