[HackerRank] Sorting-Running Time of Algorithms

Running Time of Algorithms | HackerRank

Running Time of Algorithms | HackerRank

 

 

<문제>

input: 첫번째 줄에는 배열의 크기를 입력받고, 두번째 줄에는 배열 arr의 원소를 입력받는다.
output: 배열을 정렬하는 데 걸리는 총 shift 횟수를 출력한다.

 

 

<코드>

int runningTime(int arr_count, int* arr) {
    int * result=arr;
    int value, shift;
    
    for (int i=0;i<arr_count;i++){
        value=result[i];
        int j=i-1;
        while(j>=0&&value<result[j]){
            result[j+1]=result[j];
            shift++;
            j--;
        }
        result[j+1]=value;
    }
    return shift;

}

<풀이>

매개변수로 넘겨받은 arr 배열을 정리한 배열로 result를 선언했다. 그리고 총 shift 횟수를 저장하는 shift 변수를 선언했다. 다음으로 중첩 반복문을 통해 현재 result[i]값을 value에 넣고 만약 value가 result[i-1], 즉 result[j]보다 작으면 shift를 진행하고 shift++을 하여 횟수를 셌다. 그리고 result[j+1]=result[j]를 통해 shift를 한 칸 하고, j값을 하나씩 감소시켜서 while문을 빠져나올 때까지 shift해야하는지 검사했다. 마지막으로 총 shift 횟수를 리턴하여 문제를 풀 수 있었다.

 

 

<실행결과>