문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

이전 챌린지에서 Insertion 정렬을 구현했다. 작거나 대부분 정렬된 데이터와 함께 잘 동작하는 간단한 알고리즘이다. 그러나 대량의 정렬되지 않은 데이터에서는 오랜 시간이 걸린다. 그 이유를 보기 위해 실행시간을 분석할 것이다.

Challenge

이전 Insertion 정렬을 수정해서 정렬하는 동안 shift한 횟수를 구할 수 있나? 배열이 완전히 정렬되는 알고리즘을 만들어서 shift한 횟수를 출력해야한다. shift는 배열에서 요소의 위치가 바뀔때 발생한다. 필요하지 않은 경우 요소를 shift하지 않는다.

Function Description

runningTime 함수를 완성해라.
runningTime 함수는 아래와 같은 매개변수를 가지고 있다.

• int arr[n]: 정수형 배열

Returns

• int: 배열을 정렬하면서 shift한 횟수

Constraints

• -1 <= n <= 1001
• -10000 <= a[i] <= 10000
• i ∈ {0..(n - 1)}

Solved

Insertion Sort - Part 2를 풀었다면 해당 코드에 옮긴 횟수만 세면 쉽게 해결할 수 있다.

• Insertion Sort Part2 문제
• Insertion Sort Part2 풀이

먼저 count 변수를 선언하고 0을 할당한다.

int count = 0;

그리고 Part2 코드에서 while문 안에서 set할때마다 count를 증가시킨다.

for(int i = 1; i < arr.size(); i++){
	int temp = arr.get(i);
	int j = i - 1;

	while(j >= 0 && arr.get(j) > temp){
		arr.set(j + 1, arr.get(j));
		count++;
		j--;
	}

	arr.set(j + 1, temp);
}

count를 반환한다.

return count;

All Code

public static int runningTime(List<Integer> arr) {
	int count = 0;

	for(int i = 1; i < arr.size(); i++){
		int temp = arr.get(i);
		int j = i - 1;

		while(j >= 0 && arr.get(j) > temp){
			arr.set(j + 1, arr.get(j));
			count++;
			j--;
		}

		arr.set(j + 1, temp);
	}

	return count;
}