[프로그래머스]Lv3. 파괴되지 않은 건물(Python)

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

프로그래머스

 

문제 접근

 

그냥 주어진 대로 구현하면,

1. type 별로 적의 공격이 있을 경우 내구도 감소, 회복일 경우 내구도 증가를 반복문을 사용해 board를 갱신

2. 마지막에 반복문을 돌면서 1이상일 경우 answer을 증가 

=> O(N^3)

=> 시간 초과 발생(효율성에서 엄청 늦게 돌아감..)

 

구글링..

누진법?  skill의 영향을 누진법용 배열에 담은 후 마지막에 board에 적용

 

1. 누적합 배열 선언 

 

2. 행 기준 누적합

                      

 3. 열 기준 누적합

코드 

 

실패

def solution(board, skill):
    answer = 0
    
    for s in skill:
        type = s[0]
        r1 = s[1]
        c1 = s[2]
        r2 = s[3]
        c2 = s[4]
        degree = s[5]

        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                if type == 1:   # 적의 공격, 내구도 감소 
                    board[i][j] -= degree
                elif type == 2: # 회복, 내구도 증가 
                    board[i][j] += degree
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] >= 1:
                answer += 1
    
    return answer

 

수정

def solution(board, skill):
    answer = 0
    
    # 누적합 기록을 위한 배열 선언 => board 크기보다 우측, 하단으로 +1씩 확장  
    tmp = [[0] * (len(board[0])+1) for _ in range(len(board)+1)]
        
    for s in skill:
        type, r1, c1, r2, c2, degree = s
        
        if type == 1:
            tmp[r1][c1] -= degree
            tmp[r1][c2+1] += degree
            tmp[r2+1][c1] += degree
            tmp[r2+1][c2+1] -= degree
        else:
            tmp[r1][c1] += degree
            tmp[r1][c2+1] -= degree
            tmp[r2+1][c1] -= degree
            tmp[r2+1][c2+1] += degree
            
    # 행 기준 누적합
    for i in range(len(tmp)- 1):
        for j in range(len(tmp[0])-1):
            tmp[i][j+1] += tmp[i][j]    # 행 기준 열 값의 변화(좌->우)
            
    # 열 기준 누적합 
    for j in range(len(tmp[0])-1):
        for i in range(len(tmp)-1):
            tmp[i+1][j] += tmp[i][j]    # 열 기준 행 값의 변화(상->하)
        
    # 기존 배열에 적용
    for i in range(len(board)):
        for j in range(len(board[i])):
            board[i][j] += tmp[i][j]
            
            if board[i][j] > 0 :
                answer += 1
    
    return answer

 

문제 회고 

 

문제 자체가 쉬워 보였기에 너무 편한 마음으로 접근하였다. 정확성 테스트는 통과했으나 효율성 테스트에서 실패

결국 누적합이라는 개념을 숙지한 후에 코드를 구현해야 했다. 생소한 개념이었지만 체화시켜야 할 중요한 개념!!