[HackerRank] Max Min 📌

 

문제 

그리디 알고리즘 ...? 

n개의 값를 가지고 있는 배열 arr에서 k개를 선택하여, 그 중 가장 큰 수와 작은 수의 차이가 최소가 되는 값

 

 

 

 

다른 사람 풀이

 

 

package hackerrank;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class MaxMin {

	public static void main(String[] args) {
		
		/*
		 * n개의 숫자가 들어있는 배열 arr, 그 중에서 k개를 뽑아서 배열 arr2를 만들어
		 * k개가 있는 배열 arr2에서 max와 min의 차이 구함
		 * 그 차이가 가장 작은 것이 답
		 */
		
		int[] array = arr.stream().mapToInt(i -> i).toArray();
		
		// 배열 정렬 (큰 값, 작은 값 구하기 쉽게)
		Arrays.sort(array);
		
		// 최소값 설정
		int minUnfairness = Integer.MAX_VALUE; 
		
		// 배열을 처음부터 (배열길이-k개+1) 만큼 돌기(연속적인 k개 선택)
		for(int i=0; i < array.length - k + 1; i++) {
			// k개 중 가장 큰 값 - 가장 작은 값
			int value = array[i + k - 1] - array[i]; 
			
			if(minUnfairness > value) {
				minUnfairness = value;
			}
		}
		
		System.out.println("minUnfairness : " + minUnfairness);
		
	}
}

 

 

 

일단 정렬 (가장 작은 수와 가장 큰 수를 찾기 쉽게 하기 위해)

배열에서 연속된 k개를 뽑을거야 ( -> 연속된 숫자의 차이가 가장 작을 확률이 높으니까 -> 시간 복잡도 낮아짐 )

for문을 돌면서 i=0 부터 i < arr.length - k + 1 까지 뽑음

 

왜 arr.length - k + 1 ? 

연속된 k개를 뽑으니까 

10개 중 3개를 뽑을때 -> 8번 (10 - 3 + 1)

10개 중 4개를 뽑을 때 -> 7번 (10 - 4 + 1)

=> 배열의 길이 - k개 + 1 

 

배열의 가장 큰 값 = arr[i + k - 1] 

배열의 가장 작은 값 = arr[i]

 

 

 

 

너무 어렵다 ! ㅠ