Leetcode1509. Minimum Difference Between Largest and Smallest Value in Three Moves

 

1. 문제 및 접근

//1509. Minimum Difference Between Largest and Smallest Value in Three Moves

// 배열이 주어지면, 그 배열에서 3번의 움직임으로 배열 속 최소 값과 최대 값의 차이가
// 가장 작게 만들어라
// 배열의 요소를 거의 다 같게 만드는 게 제일 좋을 것 같은데
// 고정된 배열이니 슬라이딩 윈도우로 수를 조정해나가야하나 ?
// 고정된 배열 속에서 최대 최소의 위치도 모르니 투포인터로 ?
// 최소 값으로 다 바꿀 수 있다면 그 값으로 바꾸면 될 것 같고
// 최소 값으로 다 바꾸지 못한다면 그 다음 작은 수?

// 차이가 가장 작은 수로 남겨야 한다 즉  차이가 중요한거지 수 자체가 작은건 상관 x
// 그럼 배열이 3개보다 작으면, 그냥 0 반환 (같은수로 다 바꾸면 되니까) 같은 수 도 바꾸지말란 말은 없다

 

 

핵심은 정렬 후 앞뒤로 정렬된 제일 작은 값을 포함하거나, 제일 큰 값을 포함해야 한다

 

 

2. 잘못된 접근

 

public int minDifference(int[] nums) {


    int size = nums.length;

    // 1. 예외처리
    if (size <= 4) { // 4보다 작거나 깉으면 같은수를 바꾸거나, 하나씩 바꾸면 되니까 0 return

        return 0;
    }

    // 2. comparator를 쓰기 위해 int를 integer로 바꿔주기 (쓰고 싶어서)

    Integer[] numInteger = Arrays.stream(nums).boxed().toArray(Integer[]::new);
    // int 타입을 stream을 사용해서 Stream<Integer>로 box해주고 바꿔주기

    // 2. 주요로직 5개의 배열을 정렬하고 그 사이의 수의 차이가 가장 큰 3개를 제거하면 될 것 같은데 ?
    Arrays.sort(numInteger,
            new Comparator<Integer>() {



                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }

            });
    nums = Arrays.stream(numInteger).mapToInt(Integer::intValue).toArray();
    // 다시 Integer배열을 int형태의 배열로 바꿔주기


    // 3. 정렬된 수의 i번째와 i+1 번쨰와 비교해서 간극이 가장 큰 값들 찾아주기
    int[] between = new int[size - 1];

    for (int i = 0; i < size-1; i++) {

        between[i] = nums[i] - nums[i + 1];
        System.out.println("between " + i +" = "+ between[i]);


    }
    Arrays.sort(between);

    // 4. 간극이 큰 3개를 빼고 그 중에서 가장 작은 값 반환하면 도
    return between[(between.length-1) - 3];

}

 

 

1. 예외사항

 

 

먼저 배열의 크기가 4보다 작을 경우엔 아무거나 바꿔도 0이 된다.

 

그 이유는 [1,4,6,80]이라고 한다면 3개를 아무거나 한 수를 잡고 바꿔준다며

[80,80,80,80]이 되고, 1을 잡아도 4를 잡아도 똑같다 !

같은 이유로 3개의 배열도 마찬가지고, 같은 수를 계속 바꿔도 되기에

[1]의 배열이 들어와도 3번의 움직임으로 최소값과 최대값의 차이를 0으로 만들 수 있다

 

 

 

2. 정렬

정렬에서 int 배열을 오름차순으로 접근해보고 싶었다..

일반적으로 compare은 int형은 쓸 수 없어서 

Stream을 사용해 Stream<Integer>형태로 전환 후 정렬 후 다시 int 배열로 바꾸는 과정이다.

 

 

 

3. 정렬된 배열로 양 옆의 배열의 수를 비교해 차이를 between 배열에 저장

 

arr   = [1, 2, 4, 8, 9] 이라면

              V  V V   V

btw = [  1, 2, 4,  1  ]

 

 

arr[0]가 arr[1]의 차이인 2를 between 의 0번째 index에 넣어준다.

 

이런 식으로 서로의 차이를 기록하는 between[arr.size-1] 배열을 생성해주고,

 

 

 

4. 정렬 후 가장 큰 차이 3개를 빼준다.

 

TastCase는 통과해서 맞는 줄 알았으나

 

 

 

틀린 이유

 

2개의 수를 합쳐서 차이를 빼고 있기에 반례가 있다.

 

[6, 6, 0, 1, 1, 4, 6]의 배열의 경우

   V  V  V V  V V

[ 1,  0, 3, 2, 0, 0 ] 3개를 빼게 된다면 0이 된다.

 

그러나 겹쳐 있는 수들을 빼는 거라 4개를 빼게되고, 원래 정답은

 

0,1,1를 6이나 4로 바꾼 2가 정답이다.

[6, 6, 6, 6, 6, 4, 6]

[6, 6, 4, 4, 4, 4, 6]

 

(0의 차이가 나게 바꿀 수 있는 방법은 3번의 움직임으로 불가)

 

 

 

 

 

 

 

 

 

정렬에서 int 배열을 오름차순으로 접근해보고 싶었다..

일반적으로 compare은 int형은 쓸 수 없어서 

Stream을 사용해 Stream<Integer>형태로 전환 후 정렬 후 다시 int 배열로 바꾸는 과정이다.