배열을 상대값(순열 이용)으로 변환하는 방법

이는 배열의 정확한 크기는 알 필요가 없고, 정렬하는데까지 걸리는 회수 같은 것만 알면 될 때,

계산하기 쉽게 상대크기로 변환해둘 수 있다.

예를 들어서

{1000, 2000, 3000}은

{0,1,2}으로 변환하는 것이다.

 

소스 예제

// 상대크기를 이용해서 상대값으로 변환해주는 메소드
static int[] solve(int[] arr) {
    // perm 을 [0, ...,n-1] 의 순열로 변환한다.
    int size = arr.length;
    int[] result = new int[size];

    // 배열 전체 반복
    for (int i=0; i<size; i++) {
        int smaller = 0;

        // 기준이 되는 값보다 작은 값이 많을 수록 상대값이 +1 된다.
        for (int j=0; j<size; j++) {
            if (arr[j] < arr[i])
                ++smaller;
        }

        result[i] = smaller;
    }

    return result;
}

특히, 여러건의 테스트를 진행하는 코딩테스트에서, 여러 건의 케이스를 그때 그때 계산하는 것이 어려울 때,

미리 계산해두고 결과만 받아오는 방법을 사용할 수 있는데,

들어올 값이 무엇일지 모르기 때문에 사용한다.

 

예를 들어서 {10, 20, 30, 50, 40} 을 정렬하는데에는 자리를 1번만 바꾸면 정렬을 완료할 수 있다.

 

다만 이것을 정렬하나 {0,1,2,4,3}을 정렬하나 같은 회수로 움직일 것이므로(상대크기가 같음)

미리 {0,1,2,3,4}을 움직여가면서 여러 계산 케이스를 만들어두고, 들어온 값을 순열로 변환해서 계산된 값을 찾아올 때 많이 사용한다.

 

 

배열을 디버깅할 때 사용할 메소드

static void toString(int[] arr) {
    System.out.print("{");
    for (int i=0; i<arr.length; i++) {
        System.out.print(arr[i]);
        if (i + 1 < arr.length) {
            System.out.print(",");
        }
    }
    System.out.println("}");
}

배열을 만들고 위 메소드로 디버깅 하면

 

테스트 & 결과

int[] i1 = {9999, 2222, 1234, 4956};
int[] i2 = {10,70,60,20,30,40};
toString(solve(i1)); // {3,1,0,2}
toString(solve(i2)); // {0,5,4,1,2,3}