자료구조 - 배열 문제 : 가장 큰 두 수의 차

연습문제  : 가장 큰 두 수의 차

보다 큰 정수들의 배열이 주어졌다고 하자. 여기서 가능한 모든 서로 다른 두 숫자의 차이를 고려해보고, 이중 가장 큰 차이를 반환하는 함수를 적어봐. 예를 들어서, [2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23] 가 입력으로 주어졌을 경우 가장 큰 차이를 내는 숫자쌍은 50-1 = 49임.

 

• 두 수의 차에 해당하는 값을 반환하면 됨. 위 예시의 경우, 49를 반환함.
• 양의 값을 반환해야 함. 위 예시의 경우 -49가 아니라 49를 반환해야 함.
• 배열의 길이는 2보다 크거나 같다고 가정.

이 문제에는 여러 종류의 풀이법이 존재함. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어봐.

def maxTwoDiff(nums):
    nums.sort()
	return nums[-1] - nums[0]
	# nums[-1] = nums[len(nums)-1]

max(nums) - min(nums)

def main():
    print(maxTwoDiff([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) # 49가 리턴되어야 합니다.

if __name__ == "__main__":
    main()

>>> 이걸 내장함수를 이용해 더 효율적인 코드로 짜보면, sort() 함수로 정렬하지 않아도 돼. 

def maxTwoDiff(nums):
	return max(nums) - min(nums)  # 최댓값 - 최솟값

def main():
    print(maxTwoDiff([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) # 49가 리턴되어야 함

if __name__ == "__main__":
    main()

max, min의 시간 복잡도 : O(N)

nums.sort()의 시간 복잡도 : O(NlogN)