JUNGOL 실력키우기 1814 : 삽입정렬 횟수 세기

임의의 서로 같지 않은 수로 이루어진 수열 A를 삽입정렬을 하고자 한다.

만약 배열 A에 20, 40, 30, 10 이 들어갈 경우 다음과 같이 삽입정렬이 이루어진다.

i = 1 일 때 20, 40, 30, 10 이동수 : 0
i = 2 일 때 20, 40, 30, 10 이동수 : 0
i = 3 일 때 20, 30, 40, 10 이동수 : 1 (40이 움직이고 30이 들어감)
i = 4 일 때 10, 20, 30, 40 이동수 : 3 (20, 30, 40 이 움직이고 10이 들어감)

총 4번의 밀어내기를 통하여 삽입정렬이 완료된다.

임의의 수열 A가 주어질 경우, 수열의 숫자가 얼마나 이동하는지 출력하는 프로그램을 작성하시오.

 

처음 줄에는 수열의 개수 N(1≤N≤50)이 입력된다.
다음 줄에는 N개의 -1000 이상 1000 이하의 정수가 입력된다. 이 수들은 서로 다르다고 가정한다.

입력된 수열에 대한 전체 이동 횟수를 출력하시오.

4 20 40 30 10

4

3 -1 1 0

1

---

이전에 작성했던 삽입 정렬에서 데이터가 변경되는 경우(저 같은 경우엔 변경될 인덱스가 바뀌는 경우)의 횟수를 누적하면 될 것 같습니다.

삽입 정렬에 대해 이해한 상태라면 쉽게 해결이 가능할 것 같네요.

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
 
    cin >> n;
 
    // 데이터를 저장할 행렬 생성
    int *arr = new int[n];
 
    // 데이터 저장
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    // 이동 수를 누적할 변수
    int accMoveCount{ 0 };
 
    // 첫번째 인덱스의 값이 있는 부분을 정렬된 배열로 가정
    // 정렬된 배열로 새 데이터 위치를 지정해 삽입해 정렬한다.
    for (int i = 1; i < n; ++i)
    {
        int data{ arr[i] };
        int index{ i };
 
        // 비교할 값의 왼쪽 부터 검사해 자리를 찾는다.
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] < data) break;
            // 이동 처리
            accMoveCount++;
            arr[index--] = arr[j];
        }
 
        // 자리 확정
        arr[index] = data;
    }
 
    cout << accMoveCount << endl;
 
    delete[] arr;
}

JUNGOL) 문제은행) 실력키우기) 삽입정렬 횟수 세기