프로그래머스-쿠키 구입

문제 요약

배열 A가 있을때, sum(A[l]~[m]) == sum(A[m + 1]~A[r])이 같도록 하는 가장 큰 sum을 구하라.

첫번째 접근

• 합의 구간을 구하는 문제라 누적합을 생각하게 되었다.

• 배열의 최대 범위가 2000이라 완전탐색이 가능했다.

• 그래서 누적합을 먼저 구성하고 이중 반복문을 통해 배열을 둘로 나누어 왼쪽과 오른쪽의 누적합이 같을 때마다 max값을 갱신하였다. 마지막으로 max를 리턴하였다.

결과

• 정답율 48%

두번째 접근

• 정답율이 절반에 가까운 것을 보고 누적합이 정답이 맞구나. 라고 생각했다.

• 그러면 무엇을 수정해야 할까. 하다가 반복문 대신 투 포인터를 쓰면 더 효율적이라고 생각했고 수정했다. 선형적으로 접근이 가능하기 때문이다.

결과

• 정답율 48%

세번째 접근

• 누적합은 필요가 없었다. 애초에 완전탐색이 가능하다는 것은 효율을 따질 필요가 없었다는 말이라는 것을 간과했다.

• 핵심은 투 포인터였다. 투 포인터를 중간으로 설정하고 점차 증가시켜가며 sumL과 sumR을 비교해가는 것이다.

결과

• 정답율 100%

후기

• 복잡하게 생각한 것 같다. 혹은 투 포인터에 대한 경험이 부족했을 수도 있다. 단순하게 생각하자.