실력키우기 삽입정렬 횟수 세기(C++)

1814 : 삽입정렬 횟수 세기

제한시간: 1ms    메모리제한: 32MB
해결횟수: 488회    시도횟수: 709회   

임의의 서로 같지 않은 수로 이루어진 수열 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 이하의 정수가 입력된다. 이 수들은 서로 다르다고 가정한다.

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

[Copy] 4 20 40 30 10

[Copy] 4

[Copy] 3 -1 1 0

[Copy] 1

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/**************************************************************     Problem: 1814     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> #include    <algorithm> using namespace std;   int main() {     int n;     int * arr;     int count = 0;     cin >> n;     arr = new int[n];     for (int i = 0; i < n; ++i)         cin >> arr[i];       for (int i = 1; i < n; ++i)     {         for (int j = 0; j <= i - 1; ++j)         {             if (arr[i] < arr[j])             {                 count += i - j;                 int tmp = arr[i];                 for (int a = i-1; a >= j; --a)                 {                     arr[a + 1] = arr[a];                 }                 arr[j] = tmp;                                   break;             }         }     }     cout << count << endl;     return 0; }

삽입정렬을 풀고 바로 풀어서 그런지.. 크게 어렵지 않았다. 

숫자가 움직이는 총 횟수를 세는 문제였는데, 결국 i - j들의 합과 동일하기 때문에. 

(0번, 1번 인덱스의 교환일 경우 1회, 0번, 2번 인덱스의 교환일 경우 2회 숫자가 움직인다. 결국 i, j 인덱스의 차이와 동일)

출력 대신 i - j를 count변수에 더해 주었다. 

삽입정렬에 대한 설명은 이전 포스팅 삽입정렬 과 동일하기 때문에 생략한다.