백준 1920번: 수 찾기

2020/09/01

문제

https://www.acmicpc.net/problem/1920

코드

public static void main(String[] args) throws IOException {
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
        br.readLine();
        int[] array1 = convertStringArrayToIntegerArray(br.readLine().split(" "));

        br.readLine();
        int[] array2 = convertStringArrayToIntegerArray(br.readLine().split(" "));

        int[] answer = solution(array1, array2);

        for (int i : answer) {
            System.out.println(i);
        }
    }
}

private static int[] convertStringArrayToIntegerArray(String[] args) {
    int[] array = new int[args.length];
    int i = 0;
    for (String str : args) {
        array[i++] = Integer.parseInt(str);
    }

    return array;
}

public static int[] solution(int[] array1, int[] array2) {
    Arrays.sort(array1);

    int[] answer = new int[array2.length];

    int index = 0;
    for (int i : array2) {
        answer[index++] = Arrays.binarySearch(array1, i) < 0 ? 0 : 1;
    }

    return answer;
}

흐름

이진 탐색(Binary Search)을 위해 검색 할 array를 우선 정렬한다.
array에 value가 존재하면 1, 없으면 0으로 저장하기 위한 answer array를 생성한다.
array에 value가 존재하는 지 확인하기 위해 array2를 돌면서 element를 꺼낸다.
꺼낸 element를 이진 탐색으로 array안에서 검색해서 존재하면 1, 아니면 0을 저장한다.
결과를 return 한다.
끝.

Arrays.binarySearch

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

// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                    int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

기준이 되는 array와 array에서 검색 할 value(key)를 입력 받는다.
from index가 to index보다 작거나 같은 동안 반복하면서
두 index를 더한 값을 >>> 연산을 통해 나눈다.
1. ex) 15(10) -> 1111(2), 15 >>> 1 = 1111 >>> 1 이므로, 0111(2)가 되고 이는 10진수 7이므로 15를 2로 나눈 값과 같다.
2. ‘>>’ 연산은 부호 비트를 보존하고, ‘>>>’ 연산은 부호 비트 관계없이 무조건 0으로 채운다.
중간이 되는 index를 구해서 array의 중간 값을 구한 후
현재 값이 중간 값 보다 작은 지 큰지 비교하면서 array에 존재하는지 확인하고
존재한다면 array에서 현재 값의 index를 return하고
존재하지 않는 다면 array에서 현재 값의 가장 가까운 index를 음수로 return 한다.

결과

테스트 케이스

assertArrayEquals(new int[] {1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0}, test.solution(new int[] {1, 3, 4, 6, 9, 13, 18}, new int[] {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}));
assertArrayEquals(new int[] {1, 1, 0, 0, 1}, test.solution(new int[] {4, 1, 5, 2, 3}, new int[] {1, 3, 7, 9, 5}));
assertArrayEquals(new int[] {1}, test.solution(new int[] {1,2}, new int[] {2}));
assertArrayEquals(new int[] {0,1,0,1,0,1,0,1,0,1}, test.solution(new int[] {2,4,6,8,10}, new int[] {1,2,3,4,5,6,7,8,9,10}));

댓글 공유

백준 1920번: 수 찾기

문제

코드

흐름

Arrays.binarySearch

결과

테스트 케이스

Junggu Ji