파괴되지 않은 건물(카카오) 문제풀이

문제 

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

프로그래머스

 

문제 접근 방식

특정 범위 의 건물를 손상시키거나 회복하는 스킬들이 주어지고, 이 스킬들을 모두 사용했을 때 최종적으로 파괴되지 않은 건물이 몇 개인지 구하는 문제이다. 해당 문제는 정확성과 효율성이 나뉘며, 1차원적인 접근 이외에 다른 접근 방법은 생각나지 않아서 정확성만 맞추고 넘어갔다. 이후, 효율성을 통과하기 위해 다른 분의 블로그를 참고하였고, 해당 블로그에서는 '누적합'을 이용해서 시간을 단축 시켰다.

 

 

누적합 아이디어

특정 구간에 대해 동일한 값을 계산하기 위해서, 아래와 같이 처음 위치에는 적용할 값 N를 적어두고, 범위 끝 부분 다음 칸에 방파제 역할을 할 -N을 적어둔다. 이렇게 함으로써 처음에서 끝까지 누적합을 해주면 해당 구간에만 원하는 값을 계산시킬 수 있다.

 

이차원 배열 응용

위의 아이디어를 응용하면 되는데 약간의 차이가 있다. 시작 행에 대해서는 동일하게 시작 열와 종료  +1 에 각각 N, -N을 기입한다. 그리고 종료 행+1 부분에서는 시작 열에는 -N, 종료 열에는 +N 을 기입하여 아래와 같이 방파제를 만들 수 있다. 

 

 

 

이러한 누적 합들을 계산할 d를 선언하고, 모든 스킬들에 대해 스킬 범위의 모서리 부분을 degree 값을 기입한다. 이후 d를 행,열 순서대로 누적합을 구하면 모든 스킬을 사용했을 때의 누적 손상 및 회복 값을 구할 수 있다. 이 누적값을 board에 더해줘서 최종적으로 건물의 상태를 구할 수 있게 된다

 

 

코드

def solution(board, skill):
    n,m=len(board),len(board[0])
    d=[[0 for _ in range(m+1)] for _ in range(n+1) ]
    
    # 모든 스킬에 대해 각 스킬의 범위 모서리 부분을 degree로 초기화한다
    for type, r1,c1,r2,c2,degree in skill:
        if type==1:
            degree*=-1
        d[r1][c1]+=degree
        d[r1][c2+1]+= degree*(-1)
        d[r2+1][c1]+= degree*(-1)
        d[r2+1][c2+1]+=degree
    
    # 각 행별로 누적합을 구한다
    for i in range(n):
        for j in range(m):
            d[i][j+1]+=d[i][j]
            
    # 각 열별로 누적합을 구한다
    for i in range(n):
        for j in range(m):
            d[i+1][j]+=d[i][j]
    
    # 누적 손상 및 회복 값을 board 에 적용한다
    answer = 0
    for i in range(n):
        for j in range(m):
            board[i][j]+=d[i][j]
            if board[i][j]>=1:
                answer+=1
    return answer

 

 

회고

특정 범위에 대해 동일한 값을 적용하고 이러한 과정을 반복해야할 때 누적합을 사용하여 빠르게 처리할 수 있음을 경험할 수 있었다. 

누적합 = 모퉁이만 값을 적어두고 한번에 처리

 

 

 

 

참고 링크

https://kimjingo.tistory.com/155

[Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT