Python으로 푸는 LeetCode 599. Minimum Index Sum of Two Lists (Easy)

LeetCode 599. Minimum Index Sum of Two Lists 

주어진 두 리스트의 공통 부분을 찾아서

각각의 리스트에서 위치한 Index의 값의 합이 최소인 결과값을 리스트로 반환하시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

이 문제는 Hash Table로 문제를 풀 경우에 쉽게 풀 수 있다. 주어진 두 리스트 중 하나를 기준으로 잡은 다음, 리스트의 원소와 index를 Key, Value로 하는 hash table을 구성한다. (파이썬에서는 dictionary 컨테이너를 활용한다) 두번째 리스트를 순회하면서 dictionary에 해당 원소를 key로 하는 값이 있는지 확인하고, 있다면 value와 현재 원소의 index의 값의 합이 최소인 원소를 반환할 리스트에 담는다. 만약  value와 현재 원소의 index의 값의 합이 최소인 경우가 여러개이면 모든 레스토랑의 이름을 담아 반환하면 된다. 

파이썬 코드

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        """
        Rumtime : faster than 100.00% of PYthon3
        Memory Usage : less than 6.35 of Python3
        """
        restaurant_list = dict()
        common = True
        for i in range(len(list1)):
            restaurant_name = list1[i]
            restaurant_list[restaurant_name] = i
 
        min_index = 20000
        min_name = []
        for j in range(len(list2)):
            restaurant_name = list2[j]
            if restaurant_name in restaurant_list:
                v = restaurant_list[restaurant_name]
                if min_index > v + j:
                    min_name = [restaurant_name]
                    min_index = v + j
                elif min_index == v + j:
                    min_name.append(restaurant_name)
        return min_name