[프로그래머스] 파괴되지 않은 건물 (Swift)

[프로그래머스] 파괴되지 않은 건물 (Swift)

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

코딩테스트 연습 - 파괴되지 않은 건물

이해

처음 문제를 읽었을때는 생각보다 쉽네? 라는 마음이었습니다. 카카오 문제라서 그렇게 쉽진 않겠지... 라는 생각에 다른 방법을 생각해보려고 노력했지만 완전탐색 말고는 방법이 떠오르지 않았습니다.

 

완전탐색으로 바로 구현을 했으나 아니나 다를까 시간초과가 ㅜㅜ 어떻게 푸는지 전혀 감이 안오는 문제였어서 풀이를 찾아봤는데, 카카오 테크에서 직접 풀이를 작성해준 글이 있어서 해당 링크를 참고했습니다.

 

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

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

 

풀이를 읽어보신 분들은 아시겠지만 이 문제는 누적합 문제입니다.

 

제가 처음 시도했던 완전탐색으로 문제를 풀게 된다면 O(NMK) 의 시간복잡도를 가지게 되기 때문에 무조건 시간초과가 발생합니다. 카카오에서는 이를 누적합을 이용해 시간복잡도를 줄이고자 하였습니다.

 

간단하게 1차원 배열을 예로 들어보겠습니다. 길이가 5인 [1,2,4,9,8] 이라는 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야하는 상황이라고 가정하겠습니다. 가장 간단한 방법은 첫 인덱스부터 탐색하며 빼주는 방법이겠지만, 이런 경우에는 O(N) 의 시간복잡도를 가지게 됩니다.

 

누적합을 이용하면 이 시간을 O(1) 로 만들 수 있습니다. 일단 길이는 똑같지만 모두 0으로 초기화된 배열을 하나 더 선언합니다. 저희는 0번째부터 3번째 원소까지의 값을 바꿔줘야 하니 0번째 인덱스와 4번째 인덱스의 값에 각각 -2와 2를 더해주겠습니다.

 

다시 말하자면 바꾸고자하는 i ... j 구간에서 arr[i] 와 arr[j+1] 의 원소에 각각 degree 그리고 degree * (-1) 값을 더해주는 것입니다. 위의 예시에서는 [-2,0,0,0,2] 와 같은 모양이 될 것입니다.

 

이를 왼쪽부터 오른쪽으로 누적합하면 [-2,-2,-2,-2,0] 과 같은 형태가 됩니다. 이 원소들을 원래 배열의 원소들과 더해주면 정답을 구할 수 있습니다. 이렇게 본다면 O(N) 의 시간복잡도와 다를게 무엇이냐? 라고 생각하실 수도 있습니다. 하지만 이를 2차원 배열로 확장시켰을때는 이야기가 달라집니다.

n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n

2차원 배열을 이용할때는 행 기준 시작점과 끝점의 한 칸 뒤, 열 기준 시작점과 끝점의 한 칸 뒤, 그리고 행과 열 기준 모두 끝점의 한 칸 뒤에 위와 같은 식으로 적용합니다. 이를 위에서 아래로, 왼쪽에서 오른쪽으로 누적합하였을때 결과는 아래와 같습니다.

n n n 0
n n n 0
n n n 0
0 0 0 0

이 방법을 skill 배열의 모든 원소를 이용하여 사용한 다음 그 결과값을 원래의 배열에 더해주면 정답을 얻을 수 있습니다. 이런 방법으로 skill 의 한 원소를 O(1) 만에 처리할 수 있다는 것을 알 수 있습니다.

 

그래서 저희는 K개의 스킬을 모두 처리할 수 있는 배열을 만드는데는 O(K) 가 걸리고, 결과값을 도출하기 위해 원래 배열과 더하는 과정은 O(NM) 이 걸립니다. 따라서 해당 문제는 O(K + NM) 의 시간복잡도로 해결할수 있습니다.

코드