문제

문제출처

문제 설명

내가 뽑을 숫자의 갯수 k와 배열 arr이 주어진다.
배열에 있는 숫자중 k개를 아무거나 뽑아서 arr'이라고 한다. unfairness = max(arr') - min(arr')
unfairness의 최소값을 추출하는 문제이다.
쉽게 말해서 원래 배열
arr = [1, 2, 3, 3] 이 있는데 이중에 k = 2개를 뽑아서 unfairness를 만들면
arr' = [1, 2], [1, 3], [3, 3], [2, 3] 이렇게 네 개의 경우의 수가 나온다. 각각의 unfairness는 1, 2, 0, 1이므로 unfairness의 최솟값은 0이 된다.

문제 해결 전략

우선 나는 배열을 내림차순이나 오름차순으로 정렬하고 정렬된 배열을 가지고 k-range를 이동시키면서 모든 값을 기록한후에 마지막에 unfair이라는 벡터의 최솟값을 출력해주는 방식을 선택해보았다.

코드

#include <bits/stdc++.h>

using namespace std;

// Complete the maxMin function below.
int maxMin(int k, vector<int> arr) {
    int ma = 0, mi = 0;
    vector<int> unfair;
    sort(arr.begin(), arr.end());
    for(int i = 0;i < arr.size()-k;i++){
        ma = *max_element(arr.begin()+i, arr.begin()+k+i);
        mi = *min_element(arr.begin()+i, arr.begin()+k+i);
        unfair.push_back(ma-mi);
    }
    
    return *min_element(unfair.begin(), unfair.end());
}

코드가 매우 간결해서 좋지만 1개는 시간 초과 1개는 잘못된 답을 추출했다.

총 스코어 29.89/35점을 획득 했다.
test case
7
3
100
200
300
350
400
401
402
여기서 잘못된 답이 나왔다.

코드2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int maxMin(int k, vector<int> arr){
	vector<int> unfair;
	int mi = *max_element(arr.begin(), arr.end());
	sort(arr.begin(), arr.end());
	for(int i = 0;i <= arr.size()-k;i++){
		mi = min(mi, arr[k+i]- arr[i]);
	}
	return mi;
}

이렇게 찾게 되면 모든 경우의 k-range를 다 살펴볼 수 있고 가장 작은 값을 찾을 수 있다.