[백준] 1920번 수 찾기 (Java)

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

1920번: 수 찾기

---

문제

---

알고리즘

 

처음에는 Stack을 써서 구현하면 어떨까? 하는 생각에 Stack으로 구현했다.

물론, 정말 바보같은 생각이었다. 왜냐하면 Stack을 사용하면 N과 M을 입력받는 의미가 없어진다. 그래서 구현하는 과정에서 의심스러웠지만 꿋꿋히 구현했지만, 결과는 '시간 초과'가 떴었다..

 

그래서 무엇이 문제인지 궁금해서 바로 찾아봤다!

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

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

역시 ,, [낯선자의 랩실] 이분이 없었더라면 ,, 시작도 못했을 것 같다..

 

 

이 문제는 Stack을 사용하는 것이 아니라 이분 탐색(이진 탐색: binary search)를 사용해서 문제를 해결하면 된다!

"이분 탐색" 이란?
정말 말 그대로 이(二)분(分)을 사용해서 해당 값의 인덱스를 반환하는 것이다. 찾으려는 값을 key라고 정의하자. 이때, 찾고자하는 배열은 정렬되어 있어야 한다. 배열의 중앙값을 mid라고 할 때, mid를 기준으로 key가 왼쪽에 있는지, 오른쪽에 있는지 판단하여 이 과정을 반복하여 해당 값을 찾아 인덱스 값을 찾는 것이다!

 

그래서 나는 위에 참고한 파어 블로거 분의 과정을 따라, 총 2가지를 구현해보았다.

 

1. Arrays.binarySearch()를 사용하여 구현

2. 직접 binarySearch()를 구현

 

---

코드

 

1. Arrays.binarySearch() 사용하여 구현

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int [] arrN = new int [N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<N; i++) {
            arrN[i] = Integer.parseInt(st.nextToken());
        }
        // 이분탐색을 위한 정렬
        Arrays.sort(arrN);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<M; i++) {
            int key = Integer.parseInt(st.nextToken());

            if(Arrays.binarySearch(arrN, key) >= 0) {
                bw.write("1\n");
            }
            else {
                bw.write("0\n");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

2. binarySearch() 직접 구현

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int [] arrN = new int [N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<N; i++) {
            arrN[i] = Integer.parseInt(st.nextToken());
        }
        // 이분탐색을 위한 정렬
        Arrays.sort(arrN);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<M; i++) {
            int key = Integer.parseInt(st.nextToken());

            if(hasNumber(arrN, key) >= 0) {
                bw.write("1\n");
            }
            else {
                bw.write("0\n");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }

    /**
     * @param arrN 정렬된 배열
     * @param key 찾으려는 값
     * @return key와 일치하는 arrN의 index 값
     *          불일치일 경우, -1 반환
     */
    public static int hasNumber(int [] arrN, int key) {
        int low = 0;
        int high = arrN.length -1;

        while(low <= high) {
            int mid = (low + high) / 2;

            if(key < arrN[mid]) {
                high = mid -1;
            }
            else if(key > arrN[mid]) {
                low = mid + 1;
            }
            else if(key == arrN[mid]) {
                return mid;
            }
        }

        return -1;
    }
}