[C++] HackerRank 해커랭크 Closest Numbers 풀이

이것 또한 쉬운 문제였는데 문제 조건 까먹고 중복제거하다가 조금 시간을 소비했던 문제입니다. 

Discussions에서 중복제거 하지말라는 말 보고 정신 차림 ㅎ;

 

---

문제의 조건

1. 배열의 원소들을 오름차순 정렬한다. 

2. 큰 원소에서 작은 원소를 뺐을 때의 차 중 가장 작은 값을 가지는 짝꿍([i, i+n])을 구한다. 

3. 주어지는 배열의 모든 원소는 unique하다. (유일한 값만 들어있음)

4. 하지만 결과값은 최소값이 나오는 모든 수의 짝꿍들이 포함되어야 하기 때문에 중복되는 값들이 나올 수 있다. 

 

---

배열의 원소 내 두 수의 차 중 가장 작은 값이 나오는 짝꿍을 구하면 되니까 모든 수를 계산할 필요는 없습니다. 

그리고 1번 조건으로 오름차순 정렬을 하고나면 숫자가 작은 순서부터 큰 순서대로 차례차례 정렬되어 있습니다. 

그렇기 때문에 반복문을 int i = 1부터 시작한다면

i번째 원소에서 i - 1번째 원소를 뺀 값이 차의 최소값에 근접한 값일 것입니다. 

[1, 2, 3, 4, 5] 배열에서

3 - 2 = 1

3 - 1 = 2

4 - 3 = 1

4 - 2 = 2

4 - 1 = 3

이렇게 되기 때문에 바로 앞의 원소가 아닌 것들과는 계산할 필요도 없습니다. 

 

그렇기 때문에 아래와 같이 작성할 수 있습니다. 

 

#include <algorithm> //해커랭크 컴파일러 기준이라 algorithm 헤더만 씁니다. 

vector<int> closestNumbers(vector<int> arr) {
	
    //오름차순 정렬 하고 시작
    sort(arr.begin(), arr.end());
    
    //결과를 저장할 배열 
    vector<int> vecIntegers;
    
    //최소값을 찾아가야하기 때문에 초기값은 가장 큰 값으로 설정 
    //문제의 조건에서 arr[i]의 최대값이 10^7이라 이렇게 설정 
    int iMinDiffrenece = 10000000; //최소값을 저장할 변수
    int iCurDifference = 0; //현재값을 저장할 변수 
    
    for (int i = 1; arr.size() > i; i++)
    {
    	//현재 탐색중인 원소들의 차 
        iCurDifference = arr[i] - arr[i - 1];
        
        //만약 현재값이 최소값보다 작다면 최소값을 현재값으로 갱신하고
        //결과를 저장할 배열을 초기화 후 현재 탐색중인 원소들을 추가한다. 
        //최소값이 갱신되었기 때문에 이전 최소값의 결과들을 유지할 의미가 없음 
        if (iMinDiffrenece > iCurDifference)
        {
            iMinDiffrenece = iCurDifference;
            vecIntegers.clear();
            vecIntegers.push_back(arr[i - 1]);
            vecIntegers.push_back(arr[i]);
        }
        //현재값과 최소값이 같다면 결과를 저장할 배열에 현재 탐색중인 원소들을 추가한다. 
        else if (iMinDiffrenece == iCurDifference)
        {
            vecIntegers.push_back(arr[i - 1]);
            vecIntegers.push_back(arr[i]);
        }
    }
        
    return vecIntegers;
}

 

만약 중복값을 허용하지 않았다면 마지막에

vecIntegers.resize(unique(vecIntegers.begin(), vecIntegers.end()) - vecIntegers.begin()); 

라고 적어주면 중복제거도 완료된 결과를 얻을 수 있습니다. 

 

이번 문제는 쉽죠?

난이도도 Easy였어요.