[정렬] - 두 수의 차

두 수의 차

매개변수 nums에 수열이 주어지면 수열의 원소 중 두 수의 차가 가장 작은 쌍을 찾아 반환하 는 프로그램을 작성하세요.
수열의 원소는 유일값들로 이루어져 있습니다. 두 수의 차가 가장 작은 쌍이 여러개면 모든 쌍을 배열에 담아 반환합니다.

배열에 담는 순서는 상관없습니다. 단 두 수는 오름차순 정렬된 쌍으로 표현합니다. 정확성, 효율성테스트를 합니다.

 

 

제한사항:
• nums의 길이는 100,000을 넘지 않습니다.

• 1 <= nums[i] <= 1,000

 

 

나의 코드 

def solution(nums):
    answer = []

    nums.sort()
    M=1000
    for i in range(1,len(nums)):
        if nums[i]-nums[i-1] <M:
            M=nums[i]-nums[i-1]

    for i in range(1,len(nums)):
        if nums[i]-nums[i-1]==M:
            answer.append([nums[i-1],nums[i]])
    answer.sort(key= lambda x:x[0])
               
    return answer

print(solution([3, 8, 1, 5, 12]))
print(solution([2, 1, 3, 5, 4]))
print(solution([5, 10, 15, 20, 25, 11]))
print(solution([2, 4, 3, 1, 5, 7, 8, 12, 13, 15, 23]))
print(solution([100, 200, 300, 400, 120, 130, 135, 132, 121]))

입력받은 리스트를 정렬한 뒤 하나의 반복문으로 현재 탐색중인 i원소와 그 바로 이전 원소의 차로 우선 최솟값을 찾는다.

그 후 다시 그 반복문을 돌려 해당 최소 차를 가진 쌍이 나올때마다 answer리스트에 넣는다

 

 

정답 코드 1 (O(n^2)

def solution(nums):
    answer = []
    n = len(nums)
    minN = 1000000000
    for i in range(n):
        for j in range(i+1, n):
            diff = abs(nums[i] - nums[j])
            if diff < minN:
                minN = diff

    for i in range(n):
        for j in range(i+1, n):
            diff = abs(nums[i] - nums[j])
            if diff == minN:
                answer.append(sorted([nums[i], nums[j]]))
                
    return answer

 

 

정답 코드 2 (O(nlogN)

def solution(nums):
    answer = []
    n = len(nums)
    minN = 1000000000
    nums.sort()
    for i in range(1, n):
        diff = nums[i] - nums[i-1]
        minN = min(minN, diff)

    for i in range(1, n):
        diff = nums[i] - nums[i-1]
        if diff == minN:
            answer.append([nums[i-1], nums[i]])
             
    return answer

오 정답코드의 최소 시간복잡도와 같은 로직이다 ㅋㅋ 해-삐

음 근데 늘 풀고 정답코드를 보면서 생각하지만 난 늘 최대 최소를 찾을 때 min,max보단 If 문을 사용하는것 같다.

큰 문제는 없어 보이지만 Min,max 내장 함수를 사용하는게 더 깔끌해보이긴한다.

앞으로 의식적으로 if문대신 min,max를 사용해야겠다.