관리 메뉴

솜씨좋은장씨

[leetCode] 1200. Minimum Absolute Difference (Python) (feat.ChatGPT) 본문

Programming/코딩 1일 1문제

[leetCode] 1200. Minimum Absolute Difference (Python) (feat.ChatGPT)

솜씨좋은장씨 2023. 3. 21. 15:34
728x90
반응형

코딩 1일 1문제! 오늘의 문제는 leetCode 의 Minimum Absolute Difference 입니다.

 

Minimum Absolute Difference - LeetCode

Can you solve this real interview question? Minimum Absolute Difference - Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. Return a list of pairs in ascending order(with respect t

leetcode.com

👨🏻‍💻 문제 풀이 - SOMJANG

입력 받은 arr 리스트를 오름차순으로 정렬합니다.

sorted_arr = sorted(arr)

첫번째와 두번째 값을 활용하여 최초의 min_distance 를 구합니다.

min_distance = abs(sorted_arr[1] - sorted_arr[0])

이 값을 활용하여 최초의 distance_dict 를 만들어줍니다.

distance_dict = {min_distance: []}

정렬한 리스트에서 값을 2개씩 꺼내와 pair 를 만들고 distance 를 구한 다음

현재 min_distance 와 비교하여 현재 구한 distance 가 더 작을 경우에는 min_distance 를 distance 로 치환합니다.

distance 가 distance_dict 에 있는 값이면서 min_distance 와 같을 경우에만 pair 를 저장하게끔 했습니다.

for idx in range(len(sorted_arr) - 1):
    pair, distance = [sorted_arr[idx], sorted_arr[idx+1]], abs(sorted_arr[idx] - sorted_arr[idx+1])

    if distance not in distance_dict and min_distance > distance:
        distance_dict[distance] = []
        min_distance = distance

    if distance in distance_dict and min_distance == distance:
        distance_dict[distance].append(pair)

마지막으로 마지막 min_distance 를 활용하여 distance_dict 에서 min_distance 값을 가지는 pair 목록을 꺼내서

return 하면 끝 입니다.

👨🏻‍💻 코드 ( Solution ) - SOMJANG

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        sorted_arr = sorted(arr)

        min_distance = abs(sorted_arr[1] - sorted_arr[0])

        distance_dict = {min_distance: []}

        for idx in range(len(sorted_arr) - 1):
            pair, distance = [sorted_arr[idx], sorted_arr[idx+1]], abs(sorted_arr[idx] - sorted_arr[idx+1])

            if distance not in distance_dict and min_distance > distance:
                distance_dict[distance] = []
                min_distance = distance

            if distance in distance_dict and min_distance == distance:
                distance_dict[distance].append(pair)

        return distance_dict[min_distance]

이 문제를 ChatGPT 에게도 풀어보도록 하였습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort() # sort the array in ascending order
        min_diff = float('inf') # set minimum difference to infinity
        result = [] # initialize an empty result list
        
        # loop through the array and compare adjacent elements
        for i in range(len(arr) - 1):
            diff = arr[i+1] - arr[i] # calculate the difference between adjacent elements
            
            if diff < min_diff: # if difference is less than the current minimum difference
                min_diff = diff # update the minimum difference
                result = [[arr[i], arr[i+1]]] # start a new result list with the current pair
            elif diff == min_diff: # if difference is equal to the current minimum difference
                result.append([arr[i], arr[i+1]]) # add the current pair to the result list
                
        return result

문제를 풀면서 아 저 필요없는 pair 들이 차지하는 자원들이 너무 아까운데...? 라고 생각했습니다.

문득 ChatGPT 는 어떻게 풀까? 라는 생각이 들었고 ChatGPT 에게 문제를 풀어달라고 해보았습니다.

딱 보자마자! 아... 따로 그때 그때 찾은 min_distance 에 따라 dictionary 에 계속 저장하지않고

새로운 min_distance 가 나오면 그냥 list 를 다시 처음부터 만들면 됐네....

그리고 float('inf') 를 사용하면 무한대 값을 만들 수 있구나... 를 알게 되었습니다.

ChatGPT 가 푼 결과는! 제가 풀었던 것보다 41ms 더 빠르고 메모리를 0.8MB 덜 사용했습니다.

 

여기서 더 성능을 빠르게 해줄 순 없을까? 메모리를 더 적게 사용할 수는 없을까? 라는 질문에는 

계속 같은 답변을 내놓아 아쉬웠습니다.

 

대충 복사해서 붙여넣었는데도 이렇게 뚝딱 문제를 풀어주는게 정말 신기했습니다.

 

읽어주셔서 감사합니다.

 

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

Comments