[HackerRank] Closest Numbers

https://www.hackerrank.com/challenges/closest-numbers/problem 

Closest Numbers | HackerRank

Algorithms > Sorting

 

정렬되지 않은 배열이 주어지면, 정렬한 뒤 인접한 값과의 차가 가장 작은 값들의 배열을 반환한다.

 

 

코드

vector<int> closestNumbers(vector<int> arr) {
    vector<int> ans;
    sort(arr.begin(), arr.end());	// 정렬
    int min = arr[1] - arr[0];
    for (int i = 1; i < arr.size(); i++) {
        int val = arr[i] - arr[i-1];
        if (val == min) {	// 인접한 값의 차가 min과 같으면 배열에 push
            ans.push_back(arr[i - 1]);
            ans.push_back(arr[i]);
        }
        else if (val < min) {	// 인접한 값의 차가 min보다 작으면
            ans.clear();	// 배열 값 전체 삭제 후 배열에 push
            ans.push_back(arr[i - 1]);
            ans.push_back(arr[i]);
            min = val;	// min 값 업데이트
        }
    }
    return ans;
}

 

설명

먼저 sort 함수를 이용해 배열을 정렬한다.

정렬된 배열의 1번째 값과 0번째 값의 차를 min에 저장해둔다.

배열을 돌면서 i번째 값과 i-1번째 값의 차를 val에 저장하고, val과 min의 값을 비교한다.

만약 둘이 같다면 ans 배열에 값을 넣고,

val이 min보다 작으면 ans 배열의 값을 전체 삭제 후 값을 넣고 min을 업데이트한다.