[Programmers] 파괴되지 않은 건물

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

이차원 부분합을 이용하는 재밌는 문제였습니다.

저도 처음 보는 유형이라 카카오 테크 페이지 해설을 참고하여 코드를 작성했습니다.

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

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

 

알고리즘은 아래와 같습니다.

1. 단순 구현으로 O(N * M * skill 행의 길이)로 풀 경우 정확성 테스트는 통과하지만 효율성 테스트에서는 TLE가 발생합니다.

1.1 skill 행의 길이의 경우 고정이므로 변화를 줄 수 없지만 N * M 부분의 경우 이차원 부분합을 통해 O(1)로 압축할 경우 효율성 테스트도 통과할 수 있습니다.

1.2 우선, 일차원 부분합을 통해 예시를 들어보겠습니다. 

일차원 배열 [1, 3, 5, 7]이 있고 [0, 0] ~ [0, 2]까지 2씩 공격을 가할 경우 결과는 [-1, 1, 3, 7]이 될 것입니다. 공격을 가할 때마다 결과를 업데이트할 경우 시간 복잡도가 O(N)이 되지만 공격을 가하는 구간을 누적합으로 표현할 경우 시간 복잡도를 O(1)로 줄일 수 있습니다. 앞선 예시처럼 [0, 0] ~ [0, 2]까지 2씩 공격을 가하는 경우를 누적합으로 표현할 경우 [-2, 0, 0, 2]로 표현할 수 있습니다. 누적합을 연산하면 [-2, -2, -2, 0]이 되기 때문입니다. 정리하자면 공격 구간의 시작에 degree를 표시하고 (구간의 마지막 + 1)에 -degree를 표시하면 됩니다.

1.3 이제 1.2의 내용을 이차원으로 확장할 수 있습니다.

[0, 0] ~ [2, 2]까지의 구간에 n씩 공격을 가할 경우 이차원 누적합 배열은 아래와 같이 표현할 수 있습니다.

 

[n, 0, 0, -n]

[0, 0, 0, 0]

[0, 0, 0, 0]

[-n, 0, 0, n]

 

여기서도 1.2와 마찬가지로 공격 구간의 시작에 degree를 표시하고 (구간의 마지막 + 1)에 -degree를 표시함으로써 이차원 누적합 배열을 표현할 수 있습니다.

2. 1번의 원리를 그대로 적용해 skill 배열을 순회하면서 모든 공격/보수 구간을 이차원 부분합 배열로 표시합니다. 여기서 시간 복잡도는 O(skill 행의 길이)입니다.

3. 2번에서 표현한 부분합 배열을 계산해줍니다. 여기서 시간복잡도는 O(N * M * 2)입니다.

4. 게임 맵을 순회하면서 파괴되지 않은 건물의 수를 구해주고 반환해줍니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~