[LeetCode] 599. Minimum Index Sum of Two Lists

- Problem

599. Minimum Index Sum of Two Lists

예제 3번을 봐야 이해하기 쉽다.
즉, list1과 list2에 공통적으로 존재하는 원소 x이면서, list1.index(x) + list2.index(x)가 최소 인덱스 합을 만족하는 x를 찾는 문제이다... (?)
예제 3번을 봐야 이해하기 쉽다.

- 내 풀이 1

from collections import Counter

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        commonResult = Counter(list1) & Counter(list2)        
        answer = collections.defaultdict(int)
        
        if len(commonResult) == 1:
            return list(commonResult.keys())
        
        for key in commonResult:
            answer[key] = list1.index(key) + list2.index(key)
        
        minValue = min(list(answer.values()))
        
        return list(filter(lambda x : answer[x] == minValue, answer))

코드가 더럽다.

결과

- 내 풀이 2

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        commonResult = set(list1) & set(list2)        
        answer = collections.defaultdict(list)
        minValue = 2001
        
        for key in commonResult:
            value = list1.index(key) + list2.index(key)
            answer[value].append(key)
            minValue = min(value, minValue)

        return answer[minValue]

코드는 단순해졌지만, 주어진 배열의 크기가 1000이라 index() 함수를 사용해도 무방하겠지만, 백만 이상의 크기라면 index() 함수의 사용에는 무리가 있어 보인다.

- 내 풀이 3

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        commonResult = set(list1) & set(list2)
        dic1 = {v:i for i, v in enumerate(list1)}
        dic2 = {v:i for i, v in enumerate(list2)}
        answer = collections.defaultdict(list)
        
        minValue = 2001
        
        for key in commonResult:
            value = dic1[key] + dic2[key]
            answer[value].append(key)
            minValue = min(value, minValue)

        return answer[minValue]

주어진 배열을 hash로 변환한다면 임의의 키 값에 O(1)로 접근할 수 있다.
만약 배열의 크기가 주어진 문제보다 훨씬 더 크다면 이 방법을 고려해볼만 하다.
...
그러려나?