카카오 2022 BLIND RECRUITMENT - 파괴되지 않은 건물 (Swift)

 

2차원 공간에서 누적합 문제를 풀어보았다면 해결할 수 있었던 문제이다.

유사한 문제를 풀어본 경험이 없다면 이와같은 아이디어를 떠올리기는 쉽지 않을 것 같다.

필자도 처음 이 문제를 접했을 때는 정확도만 해결했고, 모든 TC에서 시간초과 판정을 받았다.

 

아래의 블로그에서 누적합 풀이방식과 그림을 참고하여 Swift로 작성해 시간을 통과할 수 있었다.

 

아래의 방식으로, 매 번 직사각형의 모든 범위에 값을 갱신하지 않고,

직사각형의 꼭짓점 "네 곳" ( 오른쪽 변의 두 모서리는 한 칸 더 확장하여 위치함)만 갱신해준 후,

 

마지막에 26~ 30번 코드와 같이 가로로 전파

31~36 코드와 같이 세로로 전파 해준다.

 

이후 2차원 배열을 모두 탐색하며 1보다 크게 되는 칸의 수만 센다.

 

그림 출처: https://kimjingo.tistory.com/155

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