525. Contiguous Array

늘보·2021년 10월 28일

LeetCode

목록 보기

63/69

💡 풀이

var findMaxLength = function (nums) {
  let sum = 0;
  let sumArr = [];

  for (let a = 0; a < nums.length; a++) {
    if (nums[a] === 0) nums[a] = -1;
    sum += nums[a];
    sumArr.push(sum);
  }

  let obj = {};
  obj[0] = [-1];

  for (let i = 0; i < sumArr.length; i++) {
    let cur = sumArr[i];
    obj[cur] ? obj[cur].push(i) : (obj[cur] = [i]);
  }
  console.log(sumArr);

  console.table(obj);
  let maxLen = 0;

  for (let [key, value] of Object.entries(obj)) {
    let len = value[value.length - 1] - value[0];
    maxLen = Math.max(maxLen, len);
  }

  console.log(maxLen);

  return maxLen;
};

let nums = [1, 0, 1, 1, 1, 0, 0, 1, 1];
findMaxLength(nums);

📝 결과

📝 정리

어려웠다. Hash Map 관련 문제에서 자주 나오는 유형이라고 들었는데 처음 접해서 더 어렵게 느껴진 것 같다.

먼저, 이 문제를 이해하려면 이전에 풀었던 Two Sum(링크: https://velog.io/@ken1204/1.-Two-Sum) 문제를 이해해야 한다. 이 문제의 풀이 방법 중 Hash Map을 이용한 풀이가 있는데, 이를 응용한 방법이다. (자세한 풀이는 링크로 확인하자)

이 문제는 nums = [0,1 ...] 등 두 가지의 숫자(0, 1)이 반복해서 나오게 된다. 이 중 contiguous subarray를 찾아야 하는데, 이는 subarray에 있는 0과 1의 개수가 같아야 한 다는 것을 의미한다.
만약 여기서 nums 배열의 0을 모두 -1로 바꿔준다면? subarray의 0과 1의 개수가 같아야 하기 때문에 subarray 내의 모든 요소들의 합은 0이 될 것이다.
그럼 여기서 Two Sum 문제의 풀이를 응용할 수 있는데, 모든 요소들의 합이 0이 되니까target을 0으로 잡고 cumulative sum을 만들어 준다.

  for (let a = 0; a < nums.length; a++) {
    if (nums[a] === 0) nums[a] = -1;
    
    // cumulative sum
    sum += nums[a];
    sumArr.push(sum);
  }

cumualtive sum이란, 위 코드와 같이 각 요소를 계속해서 더한 요소를 sumArr에 push 한 것을 의미한다.
예를 들어, [ 1, 8, 6, 3, 2, 5, 3 ]라는 cumulative sum이 있고, target=10이라고 가정해보자. 그럼 위의 subarray [3, 2, 5]의 모든 요소의 합이 target = 10과 같게 된다. 이는 처음 인덱스에 해당하는 1부터 5에 해당하는 인덱스까지의 합에서 1, 8, 6이라는 또 다른 subarray의 요소의 합을 빼준 값과 같다.
그럼 이 배열의 인덱스(3~5)가 cumulative sum이 아닌 원본 배열 nums의 subarray의 인덱스와 동일하게 된다. 따라서 이 예시에서 subarray의 길이는 [3,2,5]의 길이, 즉 3이 된다.
위 코드의 nums 배열의 cumulative sum은 [ 1, 0, 1, 2, 3, 2, 1, 2, 3 ]이 된다.
그리고 이 sumArr(=cumulative sum)의 요소를 key로, 인덱스를 value 값으로 가지는 hash map을 만든다.

  for (let i = 0; i < sumArr.length; i++) {
    let cur = sumArr[i];
    obj[cur] ? obj[cur].push(i) : (obj[cur] = [i]);
  }

여기서, subarray가 처음부터 시작하는 예외 케이스를 고려해야 한다. 여기서는 요소 0과 인덱스를 -1로 만들었다.

obj[0] = [-1];

이 과정을 모두 마치면, obj는 다음과 같이 구성될 것이다.

그리고 이제 subarray의 최대 길이를 구하는 것은 어렵지 않다.

 for (let [key, value] of Object.entries(obj)) {
    let len = value[value.length - 1] - value[0];
    maxLen = Math.max(maxLen, len);
  }

  console.log(maxLen);

  return maxLen;

위 코드와 같이, 각 key의 value 값에는 배열 형태(subarray에 해당)로 값이 저장되어 있을 텐데, 이 value에 해당하는 배열들이 모두 오름차순으로 정렬되어 있기 때문에, 가장 뒤에 있는 값과 가장 앞에 있는 값을 서로 빼주고, 그 값들을 key마다 비교해줘서, 가장 큰 값을 return 하면 그게 답이 된다.