코드 리뷰 부탁드립니다!!

Question

안녕하세요 선생님! 강의를 듣기 전에 혼자 풀어보았습니다. 이중 for문으로 풀어서 시간복잡도 상으로는 좋지 않을 것 같은데 이것도 괜찮은 코드일까요?   function solution(k, arr) { let answer = 0; let sum = 0; let check = 0; for (let i = 0; i < arr.length - 2; i++) { for (let j = 0; j < k; j++) { sum += arr[i + j]; check += 1; } answer = Math.max(answer, sum); sum = 0; check = 0; } return answer; } let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15]; console.log(solution(3, a));

김태원 · Answer

안녕하세요^^ 강의 듣기 전에 2중 for문으로 해결한 것 만으로도 잘 하신겁니다. 그래도 영상의 슬라이딩 윈도우를 통한 단일 for문으로 해결하는 방법을 잘 익혀두세요. 실제 코테에서 이 문제를 2중 for문으로 짜면 시간초과가 날 가능성이 높습니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 코드를 살펴보니 투 포인터(Two Pointer) 알고리즘을 이용한 코드 같습니다. 시간복잡도는 O(N*K)로 나쁘지 않지만, N과 K의 입력 범위에 따라서는 시간 초과가 발생할 수도 있습니다. 만약에 입력값이 큰 경우 시간 복잡도를 좀 더 줄이기 위해 다른 알고리즘을 사용할 필요가 있습니다. 한 가지 예로는 최대 부분합 알고리즘이 있습니다. 이 알고리즘을 사용하면 시간복잡도 O(N)으로 풀이가 가능합니다. 참고로, 이 문제는 백준 알고리즘( https://www.acmicpc.net/problem/2559)에서 문제로 출제되었습니다. 백준에서는 시간복잡도를 줄이기 위해서 위와 같이 최대 부분합을 이용한 풀이가 일반적입니다. 최대 부분합 알고리즘에 대해서는 구글링을 통해 자세히 공부해보시기 바랍니다. 코드 리뷰 요청해주셔서 감사합니다. 좋은 하루 되세요!