LeetCode 599. Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists

문제

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

두 배열이 공통적으로 가지고 있는 값을 반환하는 문제인데, 그 중 두 요소의 인덱스 합이 제일 작은 값을 반환해야 한다. 최소 인덱스 합을 가지는 요소가 여러 개일 경우 모두 반환.

입출력 예

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

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

제한 사항

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] and list2[i] consist of spaces ' ' and English letters.
• All the stings of list1 are unique.
• All the stings of list2 are unique.

풀이

나의 풀이

1. 첫 번째 배열을 순회하면서 객체 map에 레스토랑 이름을 key로, 해당 인덱스를 value로 추가
2. 두 번째 배열을 순회하면서 map에 해당 요소가 존재한다면 common이라는 새로운 배열에 [배열1의 index + 배열2의 index, 중복되는 요소 값] 형태로 push
3. 두 index의 합을 기준으로 오름차순 정렬
4. common 배열을 순회하면서 두 index의 합 중 제일 작은 요소인 첫 번째 값을 기준으로 비교한다.
   첫 번째 값과 일치하는 것이 있으면 answer에 push하고, 일치하지 않으면 더 큰 값만 남게 되는 것이므로 반복문을 빠져나온다.

// Runtime: 185 ms, faster than 25.71%
// Memory Usage: 53.7 MB, less than 7.68%

var findRestaurant = function(list1, list2) {
  let map = {};
  let common = [];
  let answer = [];

  for (let i = 0; i < list1.length; i++) {
    map[list1[i]] = i;
  }

  for (let i = 0; i < list2.length; i++) {
    if (map[list2[i]] !== undefined) {
      common.push([map[list2[i]] + i, list2[i]]);
    }
  }

  common.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < common.length; i++) {
    if (common[i][0] === common[0][0]) {
      answer.push(common[i][1]);
    }
    else break;
  }
  
  return answer;
};

다른 풀이

가독성과 성능이 모두 떨어지는 풀이 같아서 다른 방법을 생각해봤다. 가독성을 높이기 위해서 Map을 사용하였고, 성능을 높이기 위해서는 최소 인덱스 합(minSum)과 반복문 내부에서 사용할 인덱스 합(sum)을 변수로 만들어서 관리했다. 현재 값의 sum과 저장되어 있는 minSum을 비교하여 일치하면 common 배열에 추가해주고, 현재 값의 sum이 minSum보다 작으면 현재 값을 담은 배열을 할당해주었다.

// Runtime: 155 ms, faster than 44.82%
// Memory Usage: 48.1 MB, less than 81.07%

var findRestaurant = function(list1, list2) {
  let map = new Map();
  let common = [];
  let minSum = list1.length + list2.length;

  for (let i = 0; i < list1.length; i++) {
    map.set(list1[i], i);
  }

  for (let i = 0; i < list2.length; i++) {
    if (map.has(list2[i])) {
      let sum = i + map.get(list2[i]);
      if (sum === minSum) {
        common.push(list2[i]);
      }
      else if (sum < minSum) {
        common = [list2[i]];
        minSum = sum;
      }
    }
  }

  return common;
};