[알고리즘/자바스크립트] Codility, MaxSliceSum 문제 풀이

"slice"라는 단어에서 파생된 썸네일 사진...🙈

MaxSliceSum

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

 

Write a function:

function solution(A);

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

 

For example, given array A such that: [3, 2, -6, 4, 0]

 

the function should return 5 because:

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

 

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be an integer within the range [−2,147,483,648..2,147,483,647].

 

---

 

오늘 풀어본 문제는 여기 저기서 자주 나오는 문제이다.

 

예전 부트캠프에서도 비슷한 문제를 풀었던 기억이 있고 여러 알고리즘 사이트에 항상 단골로 있는 문제다.

그런데 오랜만에 풀어봤더니 기억이 다 리셋됐는지 어떻게 푸는 지 한참 고민하다가 여러 시행착오 끝에 풀었다.

 

문제는 간단하다. 음수를 포함하여 숫자가 든 배열이 주어졌을 때

해당 배열에서 연속적인 숫자의 합이 가장 큰 숫자를 리턴하는 문제이다.

 

예를 들어서 배열이 [3, 2, -6, 4, 0]이 주어진다면 연속하는 숫자의 합이 3 + 2인 5가 가장 크기 때문에 5를 리턴해야 한다.

만약 배열의 숫자가 모두 음수라면, 즉 [-1, -5, -2, -7]이라면 제일 큰 음수인 -1이 리턴되어야 한다.

(음수끼리는 더할 수록 점점 더 숫자가 작아지므로...)

 

 

function solution(A) {
  let max = 0;

  A.reduce((sum, currentNum) => {
    if ((sum + currentNum) < max) {
      return 0;
    }

    return max = sum + currentNum;
  }, 0);
    
  return max;
}

 

처음에 음수를 제대로 고려하지 않고 위와 같이 풀었다가 테스트 케이스 대부분에서 틀려서 25점이 나왔다. 😂

 

대충 컨셉은 이렇다.

• max라는 변수에 초기값 0을 할당해둔다.
• A 배열을 순회하면서 누적해서 더한 값, sum에 현재 숫자를 더해서 max 변수와 크기를 비교한다.
• max보다 크기가 작으면 답이 될 수 없으므로 누적값을 0으로 초기화시키고,
• max보다 크기가 크거나 같으면 현재 숫자를 누적한 값을 max에 할당한다.
• 순회가 끝나면 max를 리턴한다.

 

이렇게 되면 음수가 섞여있으면 죄다 음수를 무시하고 0을 리턴해버리는데다가

음수만 있는 배열은 무조건 0을 리턴하게 되어 버린다.

 

그래서 0을 고려해서 다시 고민 고민한 끝에 다음과 같이 문제를 풀었다.

 

function solution(A) {
  let max = 0;

  const sum = A.reduce((prevSum, currentNum) => {
    let nextSum = prevSum + currentNum;
 
    if (nextSum < 0) {
      return 0;
    }

    if (nextSum < max) {
      return nextSum;
    }

     return max = nextSum;
  }, 0);

  return max === 0 ? Math.max(...A) : max;
}

 

• 누적된 값에 현재 숫자를 더한 값, nextSum이 0보다 작으면 누적된 값을 0으로 초기화한다.
• 만약 0보다 작지는 않지만 max보다 작으면 그 숫자에 계속 값을 누적한다.
• 만약 max보다 크다면 max를 그 누적 값으로 교체한다.
• 배열의 순회가 끝나고 max 변수의 값이 0이라면 배열의 값들이 모두 음수나 0이라는 뜻이므로, A 배열의 Max 값을 구해 return한다.
• 0이 아니라면 max 값을 바로 리턴하면 된다.

 

2중 반복문이 있거나 하지 않고 flat하게 배열을 순회하면 답이 나오기 때문에 O(N)의 시간 복잡도를 가진다.