해커랭크 - Lily's Homework

릴리의 숙제를 도와줘야 한다.

숙제의 내용은 다음과 같다.

사이즈가 n인 임의의 배열에서 n보다 작은 i들에 대해
|arr[i] - arr[i-1]|의 합들이 최소가 되도록 배열을 재배치 한다.

재배치 할 때는 두 원소의 값들만 바꿀 수 있다.(스왑)

이 때 필요한 스왑의 최소 횟수를 구하는 문제이다.

문제풀이 전략

|arr[i] - arr[i-1]|들의 합이 최소가 되도록 하기 위해서는 배열이 정렬된 상태가 되어야 한다.

정렬된 상태로 만들 때 필요한 스왑 횟수를 구하는 문제이다.

중요한 점은 오름차순으로 만들 때와 내림차순으로 만들 때의 스왑 횟수는 서로 다르므로, 두 경우를 다 구한 후 더 작은값을 반환해야 한다.

스왑을 활용한 정렬을 하기 위해서는 매번 최대(최소) 값을 구해 앞에서 부터 스왑하는 선택정렬을 사용해야 한다.

이때 주어질 수 있는 배열의 길이가 10^5 로 제한되어 있으므로 일반적인 선택정렬로는 해결할 수 없다.(O(n^2))

최대(최소)값을 찾는데 O(n)이 들던 선택정렬을 Map 자료구조를 활용하여 최대(최소)값을 뽑아낸다면 O(logn)으로 해결할 수 있다.

즉, Map을 사용한다면 O(nlogn)으로 문제를 해결할 수 있다.

풀이 순서는 다음과 같다.

1. 우선 오름차순과 내림차순으로 정렬되는 Map을 두개 선언한다.
   1.1. Map에는 수와 인덱스가 저장되도록 한다.
2. 두개의 수정될 배열을 만들어 값을 복사해서 집어넣는다.
3. 각 경우에 대해 Map을 순회하며 수가 있어야 할 위치가 아닌 경우 두 위치를 스왑해 준다.
   3.1. 이 때 스왑 후 Map의 value도 갱신해 줘야 한다.
4. 얻은 두 값 중 더 작은 값을 반환한다.

코드

int lilysHomework(vector<int> arr) {
    vector<int> arr2;
    for(int i=0;i<arr.size();i++){
        arr2.push_back(arr[i]);
    }
    map<int, int> m;
    map<int, int> mm;
    for(int i=0;i<arr.size();i++){
        m.insert(make_pair(arr[i],i));
        mm.insert(make_pair(-arr[i],i));
    }
    
    int idx = 0;
    int cnt = 0;
    for(auto iter = m.begin();iter != m.end();iter++){
        if(iter->second == idx){
            idx++;
            continue;
        }
        int tmp = arr[idx];
        arr[iter->second] = arr[idx];
        arr[idx] = iter->first;
        m[tmp] = iter->second;
        idx++;
        cnt++;
    }
    int id = 0;
    int ct = 0;
    for(auto iter = mm.begin();iter != mm.end();iter++){
        if(iter->second == id){
            id++;
            continue;
        }
        int tmp = -arr2[id];
        arr2[iter->second] = arr2[id];
        arr2[id] = -iter->first;
        mm[tmp] = iter->second;
        id++;
        ct++;
    }
    return min(cnt,ct);
}

출처
https://www.hackerrank.com/challenges/lilys-homework/problem?isFullScreen=true