[HackerRank] Running Time of Algorithms

6주차 자료구조 복습 문제
Prepare > Algorithms > Sorting

 

풀이

삽입정렬을 사용하여 배열의 원소를 정렬할 때, 자리가 변경되는 횟수를 반환하는 문제이다. 먼저 원래 알고있던 삽입정렬 알고리즘을 활용하여 코드를 작성하였다. 그 뒤, 자리가 변경되는 곳에서 cnt의 횟수를 증가시키고 배열이 완전히 정렬된 후 cnt값을 반환하였다.

int runningTime(vector<int> arr) {
    int cnt, data, i, j;
    for(i=1; i<arr.size(); i++){
        data = arr[i];
        for(j=i-1; j>=0&&arr[j]>data; j--){
            ++cnt;
            cout<<cnt<<" "<<arr[i];
            arr[j+1] = arr[j];
        }
        arr[j+1] = data;
    }
    return cnt;
}

 

결과