[LeetCode] Minimum Index Sum of Two Lists

1.문제

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

두개의 배열 list1 , list2 가 주어질 때 두 배열에 공통으로 있는 요소의 각 배열에서의 index의 합이 가장 작은 요소들의 배열을 리턴하는 문제이다.

Example 1

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

Example 2

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".

2.풀이

1. 이중 for문을 돌면서 두 배열의 요소들을 비교한다.
2. 같은 요소를 발견할 때 마다 index의 합을 구한다.
3. 여태까지의 index 합보다 현재 index 합이 더 작다면 result 배열을 비우고 현재 요소를 push한다.
4. 만약 index 합이 여태까지의 index 합이랑 같다면 result 에 push 한다.

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
const findRestaurant = function (list1, list2) {
  let result = [];
  let maxSum = Infinity;

  for (let i = 0; i < list1.length; i++) {
    for (let j = 0; j < list2.length; j++) {
      // for 문을 돌면서 두 배열의 요소들을 비교한다.
      if (list1[i] === list2[j]) {
        // 만약 두 요소가 같다면 index의 합을 구한다.
        const indexSum = i + j;
        // 만약 index의 합이 지금까지 가장 작은 index 합이라면 result 를 빈 배열로 초기화 하고 현재 요소를 push 한 후 index 합의 최댓값을 갱신한다.
        if (maxSum > indexSum) {
          result = [];
          result.push(list1[i]);
          maxSum = indexSum;
          // index의 합이 max 값과 같다면 result 배열에 현재 요소를 push
        } else if (maxSum === indexSum) {
          result.push(list1[i]);
        }
      }
    }
  }

  return result;
};

3.결과