23.04.12 파이썬 코딩 퀴즈#216 파괴되지 않은 건물 (프로그래머스 스쿨)

이번 문제는 파괴되지 않은 건물이다.

문제 설명이 제법 길기 때문에 천천히 읽어보며 머리를 써보자.

적과 아군의 스킬범위는 직사각형 범위이다.

위 그림은 건물의 크기가 4X5 이고, 내구도가 5인 상태이다.

전체 범위에 공격을 4번 받게되면 전체 내구도는 1이 된다. (공격 한번에 1씩 감소한다.)

두번째 공격은 (2,0)에서 (2,3)까지 2번 진행되었으며 이때 해당 범위의 내구도는 -1이 된다.

세번째에는 아군의 회복 스킬을 사용하여 (1,0)에서 (3,1) 영역의 건물의 내구도를 2씩 올려주었다.

이 때, (2,0), (2,1) 의 건물은 파괴되었다가 다시 복구된다.

마지막으로 (0,1)에서 (3,3)까지 범위의 공격을 1번 받게 되면, 위 그림과 같이 총 10개의 건물이 파괴가 된다.

그리고 최종적으로 남은 건물의 수를 계산하여 반환하면 된다.

제일 중요한 제한사항(문제 추가 설명)이다.

skill 의 경우 type, r1,c1,r2,c2, degree 순서로 전달되며  type 1은 공격 type 2는 회복을 degree 수치만큼 실행한다.

 

입출력 예 1번은 위 그림설명과 같다.

입출력 예를 최종 실행한 모습이다.

 

이제 코드를 작성해 보자

시험삼아 바로 싸이트에서 작성한 코드이다. 역시 모든 테케는 통과하지만 효율성 테스트에서 모두 시간 초과가 된다.

이제 효율성을 높이는 방법을 생각해보자.

 

구글링을 통해 누적합을 이용하여 정리하는 방법을 찾았다.

누적합을 사용하게 되면 위 코드처럼 O(N)의 복잡도를 가지고 전부 탐색하던 방식을 O(1)시간복잡도를 가지는 방식으로 해결함으로써 처리시간을 굉장히 단축 시켜 줄 수 있다.

위 그림처럼 값을 변화시켜야 하는 범위가 0 ~ 3까지 라면, 0과 4에만 값을 4번에는 부호만 반대로 해서 전달한다.

그 다음 누적값을 채워 넣는데, arr[i] 의 값은 arr[i-1]의 값과 현재값의 합이 된다.

만약 데미지와 수리가 동시에 들어가는 경우에도 무리없이 계산 가능하다.

2차원 배열인 경우에는 조금 생각해야 할 부분이 많아 진다.

녹색 부분을 N으로 가득 채운다고 가정하면 위와 같은 형태로 나타내야 한다.

먼저 각 행을 먼저 계산을 하고, 그 다음은 열을 기준으로 계산을 진행해야 한다.

이렇게 공부를 하고 보면 코드 자체는 특별할게 하나 없는 코드이다. 물론 다른 분들의 풀이를 보니 더 간결하게도 작성 하였는데, 공부를 목적으로 하는 내 코드에선 간결함 보다는 보고 이해하는 코드가 우선이다.