백준/1920 수 찾기 /이분탐색 ,이진탐색, Map

수 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

174862

52356

34749

29.856%

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

---

풀이

/*
완전탐색으로 풀려고하면 10만 * 10만으로 시간초과가 발생할것이 뻔하였다.
Map을 이용하여 containsKey를 사용하면 O(1)로 시간안에 풀수있지않을까.
 */

하지만 원하는 수를 찾는 탐색 알고리즘 중에

이분탐색 알고리즘 O(logN)을 이용해보자.

 

아래는 Map을 이용한 코드 ( Map에서 ContainsKey의 시간복잡도는 O(1)임을 이용한 코드)

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    완전탐색으로 풀려고하면 10만 * 10만으로 시간초과가 발생할것이 뻔하였다.
    Map을 이용하여 containsKey를 사용하면 O(1)로 시간안에 풀수있지않을까.
     */
    static int n;
    static int m;
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] nInput = br.readLine().split(" ");
        for (int i=0;i<n;i++) {
            map.put(nInput[i], i);
        }

    }

    static void solve() throws IOException {
        m = Integer.parseInt(br.readLine());
        String[] mInput = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            String currentNumber = mInput[i];
            if (map.containsKey(currentNumber)) {
                bw.write(1 + "\n");
            } else {
                bw.write(0+"\n");
            }
        }

    }

}

 

이분탐색 (이진탐색) 이용

재귀이용

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



public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    완전탐색으로 풀려고하면 10만 * 10만으로 시간초과가 발생할것이 뻔하였다.
    Map을 이용하여 containsKey를 사용하면 O(1)로 시간안에 풀수있지않을까.
     */
    static int n;
    static int m;
    static int[] numbers;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];

        String[] nInput = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(nInput[i]);
        }
        Arrays.sort(numbers);

    }

    static void solve() throws IOException {
        m = Integer.parseInt(br.readLine());
        String[] nInput = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            binarySearch(0, n - 1, Integer.parseInt(nInput[i]));
        }

    }

    static void binarySearch(int left, int right, int target) throws IOException{
        int mid = (left + right) / 2;

        if (numbers[mid] == target) {
           bw.write(1+"\n");
           return;
        }
        if (left > right) {
            bw.write(0+"\n");
            return;
        }
        if (target > numbers[mid]) {
            binarySearch(mid + 1, right, target);
        } else {
            binarySearch(left, mid - 1, target);
        }


}


}

 

반복문을 사용하는게 더 효율적이라하여

반복문 코드로 수정

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



public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    완전탐색으로 풀려고하면 10만 * 10만으로 시간초과가 발생할것이 뻔하였다.
    Map을 이용하여 containsKey를 사용하면 O(1)로 시간안에 풀수있지않을까.
     */
    static int n;
    static int m;
    static int[] numbers;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];

        String[] nInput = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(nInput[i]);
        }
        Arrays.sort(numbers);

    }

    static void solve() throws IOException {
        m = Integer.parseInt(br.readLine());
        String[] nInput = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            boolean isSuccess = binarySearch(0, n - 1, Integer.parseInt(nInput[i]));
            if (isSuccess) {
                bw.write(1 + "\n");
            } else {
                bw.write(0+"\n");
            }
        }

    }

    static boolean binarySearch(int left, int right, int target) throws IOException{

        while (left <= right) {
            int mid = (left + right) / 2;
            if (numbers[mid] == target) {
                return true;
            }
            if (numbers[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return false;

}


}