Calculate number of inversions in array<6 kyu>

문제링크

문제

Examples

[1, 2, 3, 4]  =>  0 inversions
[1, 3, 2, 4]  =>  1 inversion: 2 and 3
[4, 1, 2, 3]  =>  3 inversions: 4 and 1, 4 and 2, 4 and 3
[4, 3, 2, 1]  =>  6 inversions: 4 and 3, 4 and 2, 4 and 1, 3 and 2, 3 and 1, 2 and 1

Goal
The goal is to come up with a function that can calculate inversions for any arbitrary array

주어진 배열을 크기순으로 정렬한다고 했을 때, 그 정렬 과정 속에서 역순인 경우가 몇 번 나오는지 구하시오

문제 접근

이 문제는 버블 정렬의 과정을 물어보는 문제라고 생각했다. 버블 정렬이란 서로 인접하는 두 원소를 비교하여 정렬하는 방식의 정렬 알고리즘이다. 이 정렬 방식은 위의 문제처럼 인접하는 두 원소를 비교하기 때문에 문제에서 요구하는바를 체크하면서 순회한다. 밑에 코드를 보면 if문에 해당하는 부분(5번~10번라인)이 체크하는 부분을 나타낸다.

이 이미지는 버블정렬이 이루어지는 과정을 예를 통해서 도식화 한 것이다. 인접한 요소끼리 교환이 이루어지는 순간이 바로 역순인 때를 나타낸다.

1	function countInversions( array ){
2	  let count = 0;
3	  for(let  i = 0; i < array.length - 1; i++){
4	    for(let j = 0; j < array.length - 1 - i; j++){
5 	     if(array[j] > array[j+1]){
6 	       const tmp = array[j];
7 	       array[j] = array[j+1];
8 	       array[j+1] = tmp;
9 	       count ++;
10	     }
11       }//for j
12     }//for i
13 	return count;
14   }

결론

위 문제는 결국 '버블정렬을 구현하시오' 의 다른 버전 문제였다. 문제를 통해서 버블정렬이란 무엇인지 다시 한 번 리뷰하게 되는 시간이었다.

참고

버블정렬이란