[hackerrank] CorrectnessAndTheLoopInvariant (삽입정렬)

[문제 링크]

https://www.hackerrank.com/challenges/correctness-invariant/problem

package hackerRank;

import java.util.Scanner;

public class CorrectnessAndTheLoopInvariant {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); //사용자로부터 값을 입력받는 스캐너 쓸거다

        int numElements = in.nextInt(); //문제의 조건임. 처음에는 배열의 크기를 입력받음

        int[] array = new int[numElements]; // 입력받은 크기를 사용해서 문제풀이에 사용할 배열 생성

        //그 담에 입력받는 애들은 위에서 만든 배열에 넣어줌
        for (int i = 0; i < array.length; i++) {
            array[i] = in.nextInt();
        }
        printArray(array);
        printArray(sort(array));
    }

    public static int[] sort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; //옮기고자 하는 대상 선택
            int j = i - 1; //대상과 비교하기 위한 용도로 쓰임

            //인덱스의 범위가 0보다 작아지면 안되고, 현재 비교 대상이 j에 해당하는 것보다 작으면
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; //현재 비교 대상을 j의 값으로 바꿈
                j--; //j에 -1을 해줌 (이전 인덱스도 비교해야되니까)
            }
            arr[j + 1] = key; //while문 조건에 해당되지 않으면 key의 위치를 찾은 것. j는 현재 비교하고자 하는 것의 왼쪽을 비교하니까 +1을 해줘야 제 위치가 됨.
        }

        return arr;
    }

    //입력받은 배열 찍어주는 메서드 요소나오고 띄어쓰기 한 번 이런 식으로. 문제 조건임
    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

루프불변성을 만족시키는 삽입정렬 코드를 완성하라는 것으로 이해함.

정렬은 타겟이 되는 하나의 인덱스를 잡고,

왼쪽과 비교해서 왼쪽이 더 크면 왼쪽의 값과 자리를 바꾸고, 그 다음 왼쪽과도 비교를 해 나가는 것이다.

 

설명이 어려운데, 

처음엔 무슨말인지 이해도 잘 안가고 삽입정렬 코드만 봤을때 무슨 말인가 싶었는데 아래 그림을 보니 이해가 갔다.