본문 바로가기

알고리즘

카카오 2022 파괴 되지 않는 건물

파이썬 (정확도만 통과) 

#skill = [type, r1, c1, r2, c2, degree]
from multiprocessing.connection import answer_challenge


def solution(board, skill):
    
    answer = 0
    
    for arr in skill:
        if arr[0] == 1 : #공격
            attack(board, arr)
        elif arr[0] == 2: #회복
            heal(board, arr)
    
    for arr in board:
        for i in arr:
            if i > 0 :
                answer += 1
                    
    return answer

def attack(board, arr):
    x1, y1, x2, y2 , degree = arr[1:6]
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            board[i][j] -= degree
    print("attck",board)
def heal(board, arr):
    x1, y1, x2, y2 , degree = arr[1:6]
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            board[i][j] += degree
    print("heal", board)
board = [[5,5,5,5,5],
         [5,5,5,5,5],
         [5,5,5,5,5],
         [5,5,5,5,5]]

skill = [[1,0,0,3,4,4],
         [1,2,0,2,3,2],
         [2,1,0,3,1,2],
         [1,0,1,3,3,1]]


print(solution(board, skill))

효율성 개선 버전

아무리 생각해도 해결방안이 떠오르지 않아, 검색을 하게 되었다.

키 포인트는 "누적 합" 이 였다...

#skill = [type, r1, c1, r2, c2, degree]
#효율성을 위해 누적합 방식으로 변경

from re import S
import ssl


def solution(board, skill):
    answer = 0
    check_board = [[ 0 for _ in range(len(board[0])+1)] for _ in range(len(board)+1)]

    for type, x1, y1, x2, y2, degree in skill:
        if type == 1:
            check_board[x1][y1] -= degree
            check_board[x2+1][y2+1] -= degree
            check_board[x1][y2+1] += degree
            check_board[x2+1][y1] += degree
        else : 
            check_board[x1][y1] += degree
            check_board[x2+1][y2+1] += degree
            check_board[x1][y2+1] -= degree
            check_board[x2+1][y1] -= degree
    
    
    for i in range(len(check_board) -1 ):
        for j in range(len(check_board[0]) -1 ):
            check_board[i][j+1] += check_board[i][j]
    
    for i in range(len(check_board) -1 ):
        for j in range(len(check_board[0]) -1 ):
            check_board[i+1][j] += check_board[i][j]

    for i in range(len(check_board) -1 ):
        for j in range(len(check_board[0]) -1 ):
            board[i][j] += check_board[i][j]
            if board[i][j] > 0 :
                answer +=1 
            
    return answer



board = [[5,5,5,5,5],
         [5,5,5,5,5],
         [5,5,5,5,5],
         [5,5,5,5,5]]

skill = [[1,0,0,3,4,4],
         [1,2,0,2,3,2],
         [2,1,0,3,1,2],
         [1,0,1,3,3,1]]


print(solution(board, skill))


참고 :

https://www.youtube.com/watch?v=MfNov_Osrt8 

https://kimjingo.tistory.com/155