[C++] HackerRank 해커랭크 Insertion Sort Advanced Analysis 풀이

해커랭크 알고리즘 문제 풀면서 처음으로 만난 Advanced 문제...!

휴 정말 이름만큼 쉽지 않았습니다 ㅠ

 

---

 

 

문제의 조건

1. 배열을 오름차순으로 삽입정렬할 때 완전히 완료될 때까지 원소들이 몇 칸 움직이는지 구하기 

 

저도 처음에 shift의 뜻을 정확하게 몰라서 몇 번 움직이는지로 생각하고 풀려 했는데 당췌 풀리질 않아서 구글링을 해 본 결과... 

원소가 원래 있던 칸에서 정렬되는 칸까지의 이동거리를 구하는 것이란 것을 알게 되었습니다. 

비트 연산자의 쉬프트 연산자를 생각하면 되나 봅니다...

---

그러면 처음에 단순하게 생각할 땐 2중 for문으로 하는 삽입정렬을 시도해서 

swap이 있을 때마다 shift count를 증가시키는 방법이 있습니다. 

하지만 2중 for문은 느리기 때문에 (O(n^2)) 배열이 길어지면 타임아웃 뜹니다...ㅠㅠ

 

그렇기 때문에 최소 시간 복잡도 O(NlogN)을 보장하는 정렬 방법을 써야 합니다. 

그러한 방법에는 퀵정렬, 합병정렬 등등이 있으나 

퀵정렬로 해 보니까 타임아웃 뜨더라고요. 

퀵정렬도 피봇의 위치에 따라 복잡도가 O(n^2)까지 나온다고 하더라고요. 

그래서 무조건 O(NlogN)은 보장하는 합병정렬을 써 보았습니다. 

 

https://blog.naver.com/ndb796/221227934987

7. 병합 정렬(Merge Sort)

 

합병정렬이 뭔지 모르시면 이 블로그 글을 참고하세요. 

지금까지 본 합병정렬 글 중에 가장 쉽게 설명하셨어요. 

이 글 없었으면 이 문제 못 풀었다 진짜..ㅋㅋ

 

//합병정렬 시 정렬된 데이터를 임시로 저장할 배열이 필요한데 
//메모리 낭비를 줄이기 위해 임시 배열은 전역변수로 선언되어야 함
//문제의 조건 중 주어지는 배열의 최대 길이는 100000이라 아래와 같이 할당 
vector<int> g_vecTmp(100000);

//1. shift의 크기가 커질 수 있기 때문에 오버플로우를 피하기 위해 모든 자료형은 long으로 맞춰주세요. 
//2. 메모리의 효율을 위해 vector를 매개변수로 받을 때엔 &를 통해 레퍼런스로 받아줍시다.
//(내부 원소의 값이 변경되어야 하기 때문에 const는 쓰지 않음)
long int Merge(vector<int>& arrInt, int iStart, int iMid, int iEnd)
{
    long int iShifts = 0;
    
    int i = iStart;
    int j = iMid + 1;
    int k = iStart;
    
    //배열을 반으로 쪼개고 쪼개서 정렬을 수행하는데 
    while (i <= iMid && j <= iEnd)
    {
        //swap할 필요 없이 임시 배열에 순서대로 저장하면 되니까 그냥 넘어감 
        if (arrInt[i] <= arrInt[j])
        {
            g_vecTmp[k] = arrInt[i];
            i++;
        }
        //큰 수가 앞에 있는 것이기 때문에 뒤에 있는 작은 수가 먼저 저장되어야 함 
        else 
        {
            g_vecTmp[k] = arrInt[j];
            j++;
            //원소의 인덱스 위치가 바뀐 것이기 때문에 원래 위치에서 이동된 위치까지의 거리를 구한다. 
            //합병정렬은 배열을 반반씩 나눈 후 나눈 배열들의 각 첫번째 원소부터 대소관계 비교 후 
            //작은 값을 임시배열에 먼저 저장하기 때문에 첫번째 while문 조건을 만족하는 범위에서는
            //최대 Mid값 인덱스까지만 저장됨
            //그렇기 때문에 Mid값보다 적은 수부터 시작하는 i를 Mid에서 뺀 값에 1을 더해주면 이동거리가 됨 
            //(자세한 건 링크글 참조하시면 이해가 빠릅니다)
            iShifts += (iMid - i + 1);
        }
        k++;
    }
    
    //첫번째 조건이 참인 경우엔 i~mid 인덱스 까지의 수들은 다 정렬된 것이고
    //mid~end까지의 값들은 정렬되지 않았음
    //아직 정렬되지 못해서 원래 배열에 남아있는 원소들도 임시배열에 차례대로 넣어준다. 
    if (i > iMid)
    {
        for (int t = j; iEnd >= t; t++)
        {
            g_vecTmp[k] = arrInt[t];
            k++;
        }
        
    }
    //여기는 반대로 i~mid 인덱스까지의 값들이 정렬되지 못한 것 
    else
    {
        for (int t = i; iMid >= t; t++)
        {
            g_vecTmp[k] = arrInt[t];
            k++;
        }
    } 
    
    //원래 배열의 start~end 인덱스 원소들의 값을 정렬된 값으로 바꿔준다. 
    while (iStart <= iEnd)
    {
        arrInt[iStart] = g_vecTmp[iStart];
        iStart++;
    }
    
    return iShifts;
}

long int MergeSort(vector<int>& arrInt, int iStart, int iEnd)
{
    long int iShifts = 0;
    
    if (iStart < iEnd)
    {
        int iMid = iStart + (iEnd - iStart) * 0.5f;
        
        iShifts += MergeSort(arrInt, iStart, iMid);
        iShifts += MergeSort(arrInt, iMid + 1, iEnd);
        iShifts += Merge(arrInt, iStart, iMid, iEnd);
    }
    
    return iShifts;
}

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

    string t_temp;
    getline(cin, t_temp);

    int t = stoi(ltrim(rtrim(t_temp)));

    for (int t_itr = 0; t_itr < t; t_itr++) {
        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;
        }
        
        //메인 함수에서는 여기만 바꿔주면 됨 
        long int result = MergeSort(arr, 0, arr.size() - 1);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

 

어드밴스드에 걸맞게 오래 걸린 문제였지만 이건 제가 합병 정렬을 잘 몰라서 발생했던 문제같고 ㅋㅋㅋ

제가 첨부한 링크글 들어가서 합병 정렬이 뭔지만 제대로 이해하셔도 금방 풀 수 있는 문제입니다. 

 

만약 제대로 쓴 거 같은데 타임아웃 뜨면 매개변수의 vector에 &를 걸어줬나 안 걸어줬나 꼭 확인해보시구요. 

매개변수로 vector를 그대로 받으면 vector의 모든 데이터를 복사하느라 메모리 부하가 생기고 처리 속도가 느려지는 원인이 되는 거 같더라고요. 

&만 걸어줘도 타임아웃 안 뜹니다. (시작주소를 참고하기 때문에)

 

그럼 화이팅!