신기한 누적합 이야기 (feat. 2022 kakao 파괴되지 않은 건물)

 

2022 kakao blind 누적합 문제의 신기했던 해결법 ❕

 

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

프로그래머스

문제 6 – 파괴되지 않은 건물

(자세한 문제 설명은 위의 링크 참고)

이 문제는 정확성과 효율성 테스트가 각각 매겨지는 문제였다

문제를 읽다보면 가장 쉽고 빠르게 생각할 수 있는 아이디어가 있는데,

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000

가 문제 조건이기 때문에, 당연히 시간초과가  날 것이다.

그러면 다른 방법을 생각해봐야하는데 🤔

첫번째로 생각했던 방법은 펜윅트리를 이용하는 것이었다. 

2차원 배열을 1차원으로 만들어서 나름 잘 구성한 것 같았지만 ..? 이 또한 시간초과가 났다.

아무리 생각해도 다른 방법이 생각이 나지 않아서, 결국 해설을 보았는데

정말 신기한 아이디어라서 + 누적합 알고리즘에 두루두루 사용하기 좋을 것 같아 적어본다!

 

이 문제의 포인트는 최대한 배열 순회를 덜 하는 것이다.

 

예를 들어 다음과 같은 1차원 배열이 있고, 파란색 영역의 요소들 값에 -2 를 한다고 가정해보자

위의 경우에는 배열의 크기가 작아 시간복잡도가 크지않지만 단순 for 문으로 누적합을 구할 경우엔 O(N)의 시간복잡도가 소요된다.

 

여기서 카카오의 제시법은 다음과 같다.

 

요소를 더하거나 빼는 시작 지점과 끝 지점 + 다음칸에 빼거나 더하는 수만큼 값을 넣어 배열을 생성한다.

이 배열을 앞에서 부터 누적하면,

위와 같이 되는데,

 

이를 원본 배열과 더하면

구하려는 구간에 -2 만큼이 적용된 것을 확인할 수 있다.

 

하지만 1차원 배열 방식으로, 이 문제를 풀면 O(N*M*K) 의 복잡도를 O(N*K)만큼은 줄일 수 있지만

이 방식 또한 시간초과가 발생한다 😥

 

따라서 이 방식을 2차원으로 확장시키는 것이 해결법이다

 

2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는

(x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같다

 

즉,

위와 같은 영역에 -2 를 한다 가정하면,

위 배열을 누적합 한 결과

원하는 영역에 -2 만큼 값이 적용된 것을 확인할 수 있다

 

이제! 문제에 적용해보자

첫번째 케이스 기준으로,

원본배열을 기준으로, skill 마다 idea 에 따라 값을 넣어줍니다. 이 때 각 case 마다 시간복잡도를 O(1) 만에 처리할 수 있으니 O(K) 의 시간복잡도가 걸리고, 이 idea 배열을 바탕으로 누적합을 구하는 과정에서 O(N*M) 의 시간을 거쳐,
O(N*M + K) 로 문제가 해결된다.

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설