[알고리즘, Java] 꽤나 사용하는 Java 메서드 알아보기

알고리즘을 풀다보면 꽤나 유용하게 사용하는 메서드가 있습니다. 

그것을 알아보고 어떻게 구현돼 있는지 어떻게 최적화 되어 있는지 확인해보도록 하죠.

 

1번은

Arrays.binarySearch

입니다.

 

이 메서드는 이분탐색을 편리하게 해주는 메서드이며, BOJ 18869번을 풀 때 다른 사람의 풀이를 통해 알게되었습니다.

Java 내부로 들어가게 되면 binarySearch를 보면 아래와 같습니다.

public static int binarySearch(int[] a, int key) {
    return binarySearch0((int[])a, 0, a.length, (int)key);
}

 

그리고 내부에 binarySearch0 으로 구현된 로직입니다.

 

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;    // 탐색의 시작 인덱스
    int high = toIndex - 1; // 탐색의 끝 인덱스 (toIndex는 범위 밖이므로 -1)

    // low가 high보다 작거나 같은 동안 반복 (탐색 범위가 유효한 동안)
    while (low <= high) {
        // 중간 인덱스를 계산 (overflow 방지를 위해 low와 high의 합을 2로 나누는 대신 shift 연산 사용)
        int mid = low + high >>> 1;
        int midVal = a[mid]; // 중간 인덱스의 값

        if (midVal < key) {
            // 중간 값이 찾고자 하는 값보다 작다면, 탐색 범위를 오른쪽으로 이동
            low = mid + 1;
        } else {
            if (midVal <= key) {
                // 중간 값이 찾고자 하는 값과 같다면, 해당 인덱스를 반환
                return mid;
            }
            // 중간 값이 찾고자 하는 값보다 크다면, 탐색 범위를 왼쪽으로 이동
            high = mid - 1;
        }
    }

    // 키를 찾지 못한 경우, 삽입 위치를 결정하기 위해 -(삽입 인덱스 + 1)을 반환
    return -(low + 1);
}

 

이런 식으로 구현이 돼 있습니다. Java를 완전 깊게 알고있는 전문가들이 짜놓은 메서드기 때문에 이런걸 보고 학습하시는 것도 좋은 방향이라고 생각합니다.

 

2 번째는 깊은 복사가 필요할 때 입니다.

- 1 번 clone()을 사용하는 경우

int[][] original = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

int[][] copy = new int[original.length][];
for (int i = 0; i < original.length; i++) {
    copy[i] = original[i].clone(); // 각 행을 개별적으로 복사
}

 

- 2번 Arrays.copyOf() 를 사용하는 경우

import java.util.Arrays;

int[][] original = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

int[][] copy = new int[original.length][];
for (int i = 0; i < original.length; i++) {
    copy[i] = Arrays.copyOf(original[i], original[i].length); // 각 행을 개별적으로 복사
}

 

 

 

여기까지가 생각보다 알고리즘을 풀다보면 꽤나 만나게 되는 유형이고, 좀 더 쉽게 사용할 수 있을 메서드입니다.

참고하셔서 풀이할 때 도움이 되셨으면 합니다.

 

오늘도 좋은 하루되세요~