[Algorism/HackerRank] Max Min

👉 문제 링크

✏️ 문제 요약

• 주어진 숫자 배열에서 k개의 숫자들 중에 (가장 큰 수 - 가장 작은 수)의 값이 가장 작은 결과를 찾아라
  = k 개의 숫자 중 2개의 숫자를 뽑아 차이가 가장 작은 결과

💡 문제 풀이

• 직관적으로 생각하면 숫자 배열을 우선 정렬하고, k번째의 수(k개 중 가장 큰 수) - 첫번째 수(k개 중 가장 작은 수)로 구함

• 하지만 주의해야 할 케이스(반례 케이스)가 2가지 존재함

  1. 2개의 숫자 차이가 0이 되는 경우
     => 동일한 2개의 숫자를 뽑아 0을 만들면 가장 작은 수가 됨

     ex:) k = 2, 주어진 배열 = [1, 2, 1, 2, 1]인 경우
     => (2, 2)를 뽑음

  2. 정렬된 상태의 k번째의 수 - 첫번째 수가 반드시 최적해를 만족하지 못 함
     => 연속된 작은 숫자, 연속된 큰 숫자 상관없이 연속성이 더 좋은 숫자 배열이 최적해를 만족함

     ex:) k = 3, 주어진 배열 = [1, 5, 6, 100, 101, 102]인 경우
     => (100, 101, 102)를 뽑음

💻 구현 코드

1. 주어진 배열을 우선 정렬

2. 반례까지 포함하여 계산을 해야하므로, 정렬된 배열을 끝까지 계산해 봐야됨

코드 보기

  public static int maxMin(int k, int[] arr) {
      Arrays.sort(arr);

      int minimizedValue = Integer.MAX_VALUE;  // 최적해를 구하기전 임시값 설정

      for (int i = 0; i < arr.length - k + 1; i++) {
          // k개의 숫자 중 가장 큰 수와 작은 수의 차이를 구함
          int temp = arr[i + k - 1] - arr[i];

          if (minimizedValue > temp) {
              minimizedValue = temp;
          }
      }

      return minimizedValue;
  }