[Leetcode]2740. Find the Value of the Partition

문제 요약

• 알고리즘 분류: 배열, 정렬
• 난이도: Medium
• 문제내용:
  • 배열 nums가 주어진다. num1과 num2를 나눠서 num1 최대값과 num2 최소값의 절대값을 구한다.
  • 위 사항에서 num1과 num2 분할하고 난뒤 결과값중 최소값을 구하여라
• 사이트 주소: https://leetcode.com/problems/find-the-value-of-the-partition/description/

문제풀이 

 이번 문제는 num1, num2 나눈다고 생각 하면 나눈것에서 모든 경우의 수를 구해야 하기 때문에 구현하는데 더 복잡할수가 있다. 그냥 두 수에서 차이중에서 최소값을 구하는데만 신경쓰면 문제 풀수 있다. 예를 들어 1번 예제에서 1, 3, 2 ,4 를 보면 예시에서는 [1, 3] , [2, 4] 에서 | 1- 2 | = 1 이라는 내용으로 설명하는데 [1] , [ 2, 3, 4] 로 나눠도 |1 - 2| = 1랑 같다.

 그래서 그냥 오름차순이나 내림 차순으로 정렬해서 양 옆 인덱스 값 차이중 가장 적은 값을 구하면 끝나는 문제이다. 여기까지 설명 하고 자세한것 코드만 보면 되기 때문에 설명은 안하겠다.

 시간 복잡도는 정렬이 주라서 O(NlogN)만큼 나온다고 보면된다.

Code

Python

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort() # 정렬
        # 차이중 최솟 값을 반환 한다.
        return min([abs(nums[i + 1] - nums[i]) for i in range(len(nums) - 1)])

Java

import java.util.Arrays;

class Solution {
    public int findValueOfPartition(int[] nums) {

        Arrays.sort(nums); // 배열 정렬

        int minNum = Integer.MAX_VALUE;

        // 최소 차이를 구한다.
        for(int i = 0; i < nums.length - 1; i++){
            minNum = Math.min(minNum, Math.abs(nums[i + 1] - nums[i]));
        }

        return minNum; 
    }
}