Lily's Homework

• 알고리즘 분류 : sorting

문제요약

주어진 배열 arr[] 가 있다.
이 배열의 각각의 원소에 대해 |arr[i] - arr[i-1]| (0 < i < n) 의 합들이 최소가 되게 만들어아 한다.
(릴리의 숙제를 빨리 끝내기 위해 조지가 그렇게 해준다는 설정...)
해당 배열을 위 조건에 맞게 만들때, 원소를 교환하는 최소횟수를 구해라.

  

ex) arr = [7,15,12,3] 이면 위 조건을 만족하는 배열은 [3,7,12,15] 이다.
이 때 최소한의 교한 횟수는 다음과 같다.

1. 3 과 7을 바꾼다. [3, 15, 12,7]
2. 7과 15를 바꾼다. [3,7,12,15]
   ==> 즉 총 2회가 된다.

접근 방식

|arr[i]-arr[i-1]| 합들이 최소라는 것은 (절댓값 기호가 씌어져 있다.)
배열이 정렬되어 있다는 것이다. (오름차순이건 내림차순이건)

즉 정렬된 배열을 만들기 위해 원소들을 몇번 교환해야 되는지 구하면 된다.

단순히 selection sort라고 생각해서 풀었으나 시간초과가 계속 났다.
selection sort 에서는 각 자리에 맞는 원소를 찾기 위해 최대 n 번의 탐색을 하는데,
이 탐색시간 때문에 시간초과가 발생한다.

  

문제를 풀기위해선 다음과 같은 방법을 써야 한다.

  

• 탐색시간을 줄이기 위해 미리 정렬된 배열을 만들어 놓는다.
• 탐색시간을 줄이기 위해 배열의 원소값을 키로 하는 해쉬맵을 만들어야 한다.
• 오름차순, 내림차순 각각의 경우에 따라 정렬하는 횟수를 모두 구해야 한다.
  (오름차순일 경우와 내림차수 일 경우 각각 정렬하는 횟수가 달라서 둘중에 작은 값이 답이된다.)

풀이 방법

오름차순 정렬 만드는 기준.
arr = [7,5,12,3]

1. 미리 정렬된 배열을 만들어 놓는다.
   sorted = [3,7,12,15]

   sort(sorted.begin(),sorted.end());

2. 원본 배열의 값을 key 로, index 를 value 로 하는 hashmap 을 만든다.

   unordered_map<int,int> um;
    for(int i=0; i<n; i++) {
        um.insert(make_pair(arr[i],i));
    } 

3. i 번째 index 에 올 숫자를 찾아야 한다.
   insertion sort라면 배열을 일일이 다 탐색했겠지만, 우리에겐 미리 정렬된 배열이 있다!
   i 번째 값이 이미 정렬된 배열의 값과 같다면 다음단계들은 진행하지 않는다.

ex) 0 번째 와야 하는 값은 3 이다.

int min = sorted[i];

4. 이제 저 min 값을 arr[i] 와 바꿔야 한다. 이 때, min 값이 있는 index를 알기 위해 hashmap 을 쓴다.

arr = [7,5,12,3] 에서 3과 7을 바꿔야 하는 것이다.
arr[0] = 3;
arr[?] = 7; // ? 을 찾기 위해 hasp map 을 쓴다.

arr 의 원소 배열이 바뀌었으므로, hash map 값도 같이 바꿔줘야 한다.

int min_idx = um[min];
um[min] = i;
um[arr[i]] = min_idx;
arr[min_idx] = arr[i];
arr[i] = min;

5. 내림차순도 위와 같은 방식으로 진행한다.

코드

위 풀이 방식을 적용하면 아래와 같다.

#include <iostream>
#include <vector>
#include <unordered_map> //hash map
#include <algorithm> //for sorting

using namespace std;

int main() {  
    int n;
    cin >> n;
    vector<int> sorted(n);
    vector<int> arr(n);
    vector<int> arr2(n);

    for(int i=0; i<n; i++) {
        cin >> arr[i];
        arr2[i] = arr[i];
        sorted[i] = arr[i];
    }
    sort(sorted.begin(),sorted.end());
    //make hsah
    unordered_map<int,int> um;
    for(int i=0; i<n; i++) {
        um.insert(make_pair(arr[i],i));
    } 

    int count = 0;

    //오름차순
    for(int i=0; i<n-1; i++) {
        int min = sorted[i];
        if(arr[i] != min) {
            int min_idx = um[min];
            um[min] = i;
            um[arr[i]] = min_idx;
            arr[min_idx] = arr[i];
            arr[i] = min;
            count++;
        }        
    }

    //내림차순
    for(int i=0; i<n; i++) {
        um[arr2[i]] = i;
    }

    int count2 = 0;
    for(int i=0; i<n-1; i++) {
        int max = sorted[n-1-i];
        if(arr2[i] != max) {
            int max_idx = um[max];
            um[max] = i;
            um[arr2[i]] = max_idx;
            arr2[max_idx] = arr2[i];
            arr2[i] = max;
            count2++;
        }
    }

    int result = count < count2 ? count : count2;
}