[JS]Leetcode #454. 4Sum II

문제

문제 링크 #454. 4Sum II

문제접근

• 4개의 배열이 들어오면 4개의 배열 중 숫자 하나 씩을 뽑아서 더했을 때 0이 나오는 경우의 수를 반환하는 문제입니다.
• 간단하게 생각했을 때는 반복문을 4번 돌리는 시간 복잡도가 O(n^4)가 되는 풀이를 생각할 수 있습니다.
• 저 역시 가장 먼저 떠올린 풀이는 반복문을 4번 돌리는 풀이였지만 아무리 생각해도 너무 비효율적인 코드 같아서 최대한 시간복잡도를 줄이는 쪽으로 고민을 많이 했습니다.

풀이과정

• 4개의 배열이 모두 같은 길이로 들어온다는게 문제에 명시되어 있었기 때문에 빈 배열일 경우 바로 0을 반환하도록 예외사항을 처리했습니다.

  if (!A) return 0;

• 값을 반환할 result와 풀이에 사용할 Map()을 선언해줍니다.

  const map = new Map();
  let result: number = 0;

• 네 개의 배열 중 앞의 두 개의 배열은 순회하며 앞서 선언한 Map()에 매핑해줍니다. 값이 없는 경우는 1로, 값이 이미 존재하는 경우 기존 값 + 1로 두 개의 배열을 전체 순회하며 값을 매핑하게 됩니다.

  for (let a of A) {
    for (let b of B) {
      map.set(-(a + b), map.get(-(a + b)) + 1 || 1);
    }
  }

• 그 다음 뒤에 있는 두 개의 배열을 전체 순회하며 앞서 매핑한 값과 연산했을 때 0이 나오는 값이 있는지 확인합니다. 만약 앞서 매핑한 값과 연산했을 때 0이 나오는 값이 존재한다면 map.get()을 통해 해당 key가 가지고 있던 값만큼을 리턴값인 result에 더해줍니다.

  for (let c of C) {
    for (let d of D) {
      result += map.has(c + d) ? map.get(c + d) : 0;
    }
  }

• 마지막으로 값을 return해주게 됩니다.

  return result;

정답 코드

function fourSumCount(
  A: number[],
  B: number[],
  C: number[],
  D: number[],
): number {
  if (!A) return 0;
  const map = new Map();
  let result: number = 0;

  for (let a of A) {
    for (let b of B) {
      map.set(-(a + b), map.get(-(a + b)) + 1 || 1);
    }
  }

  for (let c of C) {
    for (let d of D) {
      result += map.has(c + d) ? map.get(c + d) : 0;
    }
  }

  return result;
}

제출 결과

• 질문이 있으시다면 댓글로 남겨주세요. 감사합니다.