[HackerRank ] Minimum Absolute Difference in an Array

문제설명

vector에 숫자들이 입력되어 있다.

두 숫자의 절대값 차를 계산하여 가장 작은 값을 결과값으로 낸다.

 

알고리즘

1. vector sort 
2. vector 전체 순회 및 가장 작은 차(min) 계산 
3. min값 반환 

 

알고리즘은 minimumAbsoluteDifference 함수만 확인하면 된다. 

코드

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'minimumAbsoluteDifference' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

//the things that I wrote
int minimumAbsoluteDifference(vector<int> arr) {
    sort(arr.begin(),arr.end()); //sort 
    int min = abs(arr.at(0)-arr.at(1)); //get the first absolute difference
    //check each value 
    for (int i=1; i<arr.size()-1; i++) {
        if(abs(arr.at(i)-arr.at(i+1))<min)  //when I calculate absolute difference, if it is more smaller than last one
            min = abs(arr.at(i)-arr.at(i+1)); //then it will be a min value now 
    }
    return min;
}


int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string n_temp;
    getline(cin, n_temp);

    int n = stoi(ltrim(rtrim(n_temp)));

    string arr_temp_temp;
    getline(cin, arr_temp_temp);

    vector<string> arr_temp = split(rtrim(arr_temp_temp));

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        int arr_item = stoi(arr_temp[i]);

        arr[i] = arr_item;
    }

    int result = minimumAbsoluteDifference(arr);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}​

고찰

Greedy 알고리즘을 통해서 쉽게 해결할 수 있는 문제이다. 

다만 주어진 배열을 그대로 두고 문제를 해결하려하면 계산할 짝을 구하는데 복잡해진다.

 

따라서 이번 문제에서 중요한 부분은 정렬이다. 

오름차순 정렬을 진행하면 따로 절대값 차를 구할 짝을 찾을 필요가 없다. 

정렬이 된 순간 부터 절대값 차를 크게 만드는 짝은 선택지에서 배제되기 때문이다.