[백준] 1920번 : 수 찾기 - JAVA

1920 수 찾기

 

이 문제는 M개의 수가 각각 A 배열에 들어있는 지 확인하는 문제이다.

 

M개의 수가 최대 100,000개이고 시간제한은 1초이기 때문에 정렬 후 이진탐색 알고리즘을 사용하면 된다고 생각하였다.

이진탐색의 시간복잡도는 $ \log_2 N $ 이다.

 

$ 2^{16} = 65,536 $

$ 2^{17} = 131,072 $

$ 16 < \log_2 100000 < 17 $

 

 

이진탐색 구현

private static int[] arrSearch;

private static int binarySearch(int num) {
    int left = 0;
    int right = arrSearch.length - 1;

    while(left <= right) {
        int mid = (left + right) / 2;

        if (arrSearch[mid] > num) {
            right = mid - 1;
        } else if (arrSearch[mid] < num) {
            left = mid + 1;
        } else {
            return 1;
        }
    }

    return 0;
}

 

 

위 소스를 제출하고 다른 사람들은 어떻게 구현했는 지 궁금해서 찾아보다가 Stranger's LAB님의 블로그를 보게 되었다.

 

https://st-lab.tistory.com/261

[백준] 1920번 : 수 찾기 - JAVA [자바]

 

 

간단한 이진탐색의 문제여서 소스는 거의 동일하였지만 Stranger's LAB님 덕분에 현재 일 하면서 잘 사용하지 않는 비트연산자를 사용해도 된다는 점을 알게 되었다.

 

int mid = (left + right) / 2;
int mid = (left + right) >>> 1;

 

 

비트연산자 종류: <<, >>, >>>

Integer 정수형 32bit 기준으로 설명하겠다.

비트연산자

 

• << : 2 << 3의 경우 이진수를 3칸 앞으로 이동한다. $ 2 * 2^3 $
• >> : 16 >> 3의 경우 이진수를 3칸 뒤로 이동하고 최상위 부호 비트로 빈칸을 채운다. $ 16 / 2^3 $ 
• >>> : 최상위 부호 비트와 상관없이 뒤로 이동한다.

위 이미지만 봤을 때 비트연산자를 사용하며 주의해야 할 점은 4번째 이미지의 경우로, 피연산자가 음수인데 최상위 부호 비트와 상관없이 뒤로 이동하는 >>> 연산자를 사용한 것이다.

 

다시 돌아와 아래 소스는 비트연산자를 적용한 구현 소스이다.

 

성공 소스

public class _1920 {

    private static int[] arrSearch;

    private static int binarySearch(int num) {
        int left = 0;
        int right = arrSearch.length - 1;

        while(left <= right) {
            int mid = (left + right) >>> 1;

            if (arrSearch[mid] > num) {
                right = mid - 1;
            } else if (arrSearch[mid] < num) {
                left = mid + 1;
            } else {
                return 1;
            }
        }

        return 0;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        // 입력 시작
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arrSearch = new int[n];

        for (int i = 0; i < n; i++) {
            arrSearch[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] b = new int[m];

        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }
        // 입력의 끝

        // 이분탐색 전 정렬
        Arrays.sort(arrSearch);

        // 이분탐색
        for (int i = 0; i < m - 1; i++) {
            sb.append(binarySearch(b[i])).append("\n");
        }
        sb.append(binarySearch(b[b.length - 1]));

        System.out.println(sb);
        br.close();
    }

}

 

 

잠깐 다른 이야기로 위 소스에서 사용한 정렬 Arrays.sort 메소드는 내부적으로 원시타입의 경우 듀얼피봇퀵정렬 알고리즘을 사용하고 있다던데, 추후 공부를 해야겠다.

참조타입의 경우는 Collections.sort와 동일하게 팀정렬 알고리즘을 사용한다.

 

 

feat. 정렬 알고리즘 종류

/**
 * 정렬
 * 1. 계수 정렬 (Counting Sort)
 * 2. 선택 정렬 (Selection Sort)
 * 3. 삽입 정렬 (Insertion Sort)
 * 4. 거품 정렬 (Bubble Sort)
 * 5. 셸 정렬 (Shell Sort)
 * 6. 힙 정렬 (Heap Sort)
 * 7. 합병(병합) 정렬 (Merge Sort)
 * 8. 퀵 정렬 (Quick Sort)
 * 9. 이진 삽입 정렬 (Binary Insertion Sort)
 * 10. 팀 정렬 (Tim Sort)
 *
 */

 

 

 

- 참고

https://coding-factory.tistory.com/521

[Java] 비트(Shift) 연산자 사용법 & 예제