LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves 자바 문제 풀이

문제 설명

• 문제: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description
• 설명: 정수 배열에서 최대 3개의 숫자를 제거하여 나머지 숫자들의 차이값(최대값 - 최소값)를 최소화해야 합니다.

접근 방식

• 아이디어:
  • 3개의 숫자를 제거하는 모든 경우의 수를 고려합니다.
  • 리스트가 4개 이하라면 변경된 숫자끼리 차이값을 만드는게 가능하므로, 차이값은 무조건 0입니다.
  • 리스트가 5개 이후부터 변경된 숫자를 제외한 두 숫자의 차이값이 가장 작습니다.
  • 차이값이 가장 큰 값은 가장 큰수와 가장 작은수이므로, 앞에서부터 3개의 숫자와 뒤에서부터 3개의 숫자를 확인하기위해 정렬합니다.
  • 3개의 숫자를 제거할수 있으므로, 고려해야하는 수는 가장 작은수 3개와 가장 큰수 3개입니다.
  • 배열을 정렬한 후, 가능한 경우의 수는 다음과 같습니다
    1. 마지막 3개의 숫자를 제거하는 경우. [ 1 , 2 , 3 , 4 , 5 , 6 , , , _ ] 차이값 = 6 - 1
    2. 첫 1개와 마지막 2개를 제거하는 경우. [ , 2 , 3 , 4 , 5 , 6 , 7 , , _ ]] 차이값 = 7 - 2
    3. 첫 2개와 마지막 1개를 제거하는 경우. [ , , 3 , 4 , 5 , 6 , 7 , 8 , _ ]차이값 = 8 - 3
    4. 첫 3개의 숫자를 제거하는 경우. [ , , _ , 4 , 5 , 6 , 7 , 8 , 9 ] 차이값 = 9 - 4
    5. 이 중 최소 차이를 찾습니다.
    6. 가능한 경우의 수를 계산하기 위해 4번 반복해서 계산합니다.
• 알고리즘:
• 배열을 정렬합니다.
• 가능한 4가지 경우의 수에 대해 최대값과 최소값의 차이를 계산합니다.
  1. 뒤에서 4번째 값 - 1번째 값
     1. 뒤에서 세번째 값 - 2번째 값
     2. 뒤에서 두번째 값 - 3번째 값
     3. 마지막 값 - 4번째 값
     4. 계산된 차이값 중 최소값을 반환합니다.

코드

class Solution {
    public int minDifference(int[] nums) {
        if (n <= 4) return 0;

        int n = nums.length;
        int minDiff = Integer.MAX_VALUE;

        Arrays.sort(nums);

        for (int i = 0; i < 4; i++) {
            int diff = nums[n - 4 + i] - nums[i];
            minDiff = Math.min(minDiff, diff);
        }

        return minDiff;
    }
}

결론

• 시간 복잡도:
  • 배열을 정렬하는 데 O(n log n)의 시간이 필요합니다.
  • 4개의 경우를 검사하는 데 O(1)의 시간이 필요합니다.
  • 따라서 전체 알고리즘의 시간 복잡도는 O(n log n)입니다.
• 공간 복잡도:
  • 추가적인 공간을 거의 사용하지 않으므로 O(1)입니다.