[leetcode] 3043. Find the Length of the Longest Common Prefix 파이썬 코드

https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix/

 

문제: 두 개의 배열이 있을 때 arr1에서의 원소, arr2에서의 원소의 가장 긴 common prefix의 길이를 구하는 문제다.

 

class Solution(object):
    def longestCommonPrefix(self, arr1, arr2):
        arr2Set = set()
        arr2Pre = list(set(arr2))
        arr1Pre = list(set(arr1))

        # make hashset
        for num in arr2Pre:
            numStr = str(num) # "1000"
            for i in range(len(numStr)): # i = 0, 1, 2, 3
                temp = numStr[0:i+1]
                arr2Set.add(temp)

        arr1Pre = sorted(arr1Pre, reverse=True)
        maxLength = 0
        for num in arr1Pre:
            numStr = str(num) # "100"
            for i in range(len(numStr), 0, -1):
                temp = numStr[0:i]
                if temp in arr2Set:
                    maxLength = max(maxLength, len(temp))

        return maxLength

 

 

내 코드는 그렇게 효율적이지 않았다.

 

고수의 코드를 참고했다.

1234의 prefix를 hashset에 넣을 때

n = n // 10 이렇게 코드를 짜면

1234 넣고, 123 넣고, 12, 1 넣는 걸 깔끔하게 표현할 수 있다.

 

            while n:
                prefix_set.add(n)
                n /= 10

 

이렇게 하고 끝내도 되지만 좀 더 optimize 할 수 있는 방법이 있다.

배열에 1234와 12345가 있다고 하자.

그런데 12345는 사실상 5를 떼 버리면 1234이다. 

 

그래서 12345를 넣으면, 그 다음 10으로 나눈 값은 set에 넣을 필요가 없다.

            while n and n not in prefix_set:
                prefix_set.add(n)
                n /= 10

 

class Solution(object):
    def longestCommonPrefix(self, arr1, arr2):
        prefix_set = set()

        for n in arr1: 
            while n and n not in prefix_set:
                prefix_set.add(n)
                n = n // 10

        res = 0
        for n in arr2:
            while n and n not in prefix_set: 
                # n is not zero and not in prefix_set
                n = n // 10
            if n: # if n is not zero
                res = max(res, len(str(n)))
        return res

 

 

 

내 코드보다 200ms 더 빠르고, 코드가 훨씬 깔끔하다.

 

참고

https://youtu.be/06dIUJwdHlQ?si=Dlkjd0l8e8qTOxRx