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

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 최대 매출(Sliding Window)

작성

288

안녕하세요 선생님!

강의를 듣기 전에 혼자 풀어보았습니다.

이중 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));

javascript 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

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

Som

질문자

네 감사합니다!!

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

코드를 살펴보니 투 포인터(Two Pointer) 알고리즘을 이용한 코드 같습니다. 시간복잡도는 O(N*K)로 나쁘지 않지만, N과 K의 입력 범위에 따라서는 시간 초과가 발생할 수도 있습니다.

만약에 입력값이 큰 경우 시간 복잡도를 좀 더 줄이기 위해 다른 알고리즘을 사용할 필요가 있습니다. 한 가지 예로는 최대 부분합 알고리즘이 있습니다. 이 알고리즘을 사용하면 시간복잡도 O(N)으로 풀이가 가능합니다.

참고로, 이 문제는 백준 알고리즘(https://www.acmicpc.net/problem/2559)에서 문제로 출제되었습니다. 백준에서는 시간복잡도를 줄이기 위해서 위와 같이 최대 부분합을 이용한 풀이가 일반적입니다.

최대 부분합 알고리즘에 대해서는 구글링을 통해 자세히 공부해보시기 바랍니다.

코드 리뷰 요청해주셔서 감사합니다. 좋은 하루 되세요!

인프런 커뮤니티 질문&답변

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