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

문제

정렬된 리스트와 함께 정렬되지 않은 숫자 e가 오른쪽 끝에 있는 경우, 정렬된 상태를 유지하면서 e를 배열에 삽입하는 코드를 작성할 수 있나?
학습을 위한 연습이기 때문에 가장 효율적인 방법은 아닐 것이다. 대신 무차별 대입 방법을 자세히 보여줄 것이다.

Example

n = 5
arr = [1, 2, 4, 5, 3]

가장 오른쪽 인덱스에서 시작해라. arr[4] = 3의 값을 정렬해라. 각 요소들을 작은 값에 도착할때까지 왼쪽 요소와 비교해라. 아래에 결과가 있다.

1 2 4 5 5
1 2 4 4 5
1 2 3 4 5

Function Description

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

• n: arr의 크기를 나타낸 정수
• arr: 정렬할 정수형 배열

Returns

• None: 각 새로운 줄에 중간 배열과 마지막 배열을 출력해라. 반환 값은 기대하지 않는다.

Constraints

• 1 <= n <= 1000
• -10000 <= arr[i] <= 10000

풀이

가장 오른쪽 값을 가지고 선택정렬을 해야 했는데 문제를 읽지 않고 바로 선택정렬을 해서 다시 풀었다.

가장 오른쪽의 값을 변수에 먼저 할당해 놓는다.

int selectedNum = arr.get(n - 1);

반목문 안에서 많은 일이 발생한다. 해당 인덱스의 왼쪽 값과 비교해서 값을 치환하거나 치환해서 빠져나와야한다. 그리고 빠져나오지 않았다면 해당 과정을 출력한다.

for(int i = n - 1; i > 0; i--){
	if(arr.get(i - 1) > selectedNum){
		arr.set(i, arr.get(i - 1));
	}else{
		arr.set(i, selectedNum);
		break;
	}

	for(int j = 0; j < arr.size(); j++){
		System.out.print(arr.get(j) + " ");
	}
	
    System.out.println();
}

이렇게만 보면 문제가 해결된 것으로 보이지만 실행해보면 인덱스 0은 수행하지 않고 인덱스 0과 인덱스 1이 같은 값으로 출력될 수 있다. 그래서 값이 같을 때, 인덱스 0을 selectedNum값을 할당하고, 전체 리스트를 한 번 더 출력한다.

if(arr.get(0).equals(arr.get(1))){
	arr.set(0, selectedNum);
}

for(int i = 0; i < arr.size(); i++){
	System.out.print(arr.get(i) + " ");
}

전체 코드

public static void insertionSort1(int n, List<Integer> arr) {
	int selectedNum = arr.get(n - 1);

	for(int i = n - 1; i > 0; i--){
		if(arr.get(i - 1) > selectedNum){
			arr.set(i, arr.get(i - 1));
		}else{
			arr.set(i, selectedNum);
			break;
		}

		for(int j = 0; j < arr.size(); j++){
			System.out.print(arr.get(j) + " ");
		}

		System.out.println();
	}

	if(arr.get(0).equals(arr.get(1))){
		arr.set(0, selectedNum);
	}

	for(int i = 0; i < arr.size(); i++){
		System.out.print(arr.get(i) + " ");
	}
}