파괴되지 않은 건물

유승선 ·2022년 6월 9일
0

프로그래머스

목록 보기
21/48


정말 오랜만에 프로그래머스 문제를 풀게 되었다. 이 문제를 풀게 된 계기도 바로 이전에 "태상이의 훈련소 생활" 문제를 푼 후에 prefix sum 에 대한 이해도와 깊은 깨달음을 얻게 되가지고 GP에 있었을때부터 쭉 눈팅만 하고 도전할 엄두도 못했었던 2022 카카오 블라인드 리쿠르트먼트 5번 문제로 출제됐던 문제를 풀게되었다.

문제 내용은 어떻게 보면은 간단하다, board 와 skill 벡터가 따로 주어지는데 board 는 건물을 표현하고 숫자는 내구도를 나타낸다. 그리고 skill 에 있는 원소들을 보면은 총 6가지에 원소가 있는데 첫번째 원소는 공격/힐 로 이루어진 스킬이다. 공격은 1로 표현되고 공격일경우 건물의 내구도가 벡터안에 있는 마지막 숫자만큼 차감이된다. 반대로 힐은 2로 표현이 되있는데 힐인 경우는 내구도가 다시 채워진다. 그 사이에 있는 숫자들은 전부 좌표를 의미하고 x,y ~ xx,yy 까지를 나타낸다. 가령 예를 들어 [1,0,0,3,4,4] 경우에는 좌표 0,0 부터 좌표 3,4 까지 4의 공격을 한다 라는 뜻이다.

자 이 문제를 어떻게 풀수 있을까, 먼저 스킬 벡터를 읽으면서 좌표를 저장한후에 두가지 중첩 for 문을 써서 스킬에 따라서 포인트를 더하고 빼줄수 있는 방법이 있다. 다만, 이 방법을 쓸 경우에는 10만이 훌쩍넘는 계산을 해야하고 효울성을 보는 이 문제를 절대 통과못할것이다. 실제로 2022 카카오 블라인드 리쿠르트먼트 통계만 보더라도 정확성 같은경우, 50퍼센트를 넘었던거에 비교해서 효율성은 1.8 퍼센트 밖에 통과를 못했다. 그만큼 효율성으로 따졌을때 어려운 문제였다는 뜻.

오늘 배운 prefix sum (누적합) 을 이용해서 문제를 풀어야한다고 생각했다. 비록 태상이의 훈련소 생활 문제만 풀고 prefix sum에 대한 이해도를 높혔지만 그래도 도전해보고 싶었다. 내 노트에 별에별 그림을 그려보고 별에별 계산을 했었다. 그 결과, 진짜 못풀었다. 원래 내 국룰로는 내가 30분동안 고뇌해도 못푼다면 답을 참고했지만 이상하게 정말 조금만 더 하면 풀 수 있을거같아서 국룰을 어기고 세시간 정도를 딱 그 퍼즐 한조각만 가지고 고민을 했었다. 결국에는 도저히 안되겠다 싶어서 그 한조각을 위해서 답을 참고했고 너무 큰 깨달음을 얻고야 말았다.

내 코드이다. 그냥 볼때는 저게 뭐 어려운 코드인가 생각할수도 있지만 사실은 굉장히 많은 시간과 고민이 들어간 코드이다. 태상이 문제를 읽으면서 내가 너무 헷갈렸던 점은 1차원 벡터에서 구하는 누적합은 완벽히 이해했지만 2차원 벡터에서 누적합을 구한다는게 너무 말이 안된다고 생각했다. 그리고 느꼈던 점은 나는 "행" 에 대한 누적합만 구할려고 했었기 때문에 실패했던 것이였다. 내가 참고했던 답을 봐보니 2차원 벡터에서 누적합을 구하기 위해서는 "열" 에 대한 누적합도 구했어야했는데 내가 그걸 안하고 행에 덧셈에 대한 고민만 하고 있었다보니 그 마지막 퍼즐이 안풀렸었던 거다. 결국 "행" 과 "열" 에 대한 누적합 이해도가 높았다면 이런일도 절대 없었을거같다.

그 둘의 관계를 이해하면은 prefix_board 의 해당 지점에 숫자를 더해줘서 마지막에는 행에 대한 덧셈 그리고 열에 대한 덧셈을 끝내준다면 쉽게 문제를 풀 수 있었다. 자세한 풀이 는 여기를 참고 하면 더 좋을거같고 이제 prefix_sum 에 대한 생각을 너무 많이 해서 그런지 이런 비슷한 문제가 나오면 다 풀어버릴수 있을거같다. 오랫동안 건드리지 못했던 2022 카카오 문제를 풀어서 뿌듯했지만 실제로 내가 이 문제를 보게된다면 많이 당황했을거같다...

배운점:
1. prefix sum 에 대한 완전한 이해
2. 2차원 배열에 대한 누적합.

profile
성장하는 사람

0개의 댓글