[C++/JAVA] 이진탐색 (lower bound) (2021카카오 - 순위검색)

이진 탐색이란?

정렬된 데이터에서 특정 값을 찾아내는 divide n conquer 알고리즘.

탐색이 반복될 때마다 탐색 구간이 1/2씩 감소한다. (bigO logn)

원리

1. 데이터 집합의 가운데 원소(mid)와 타겟(target)을 비교

2. mid > target 인 경우 집합의 왼쪽 1/2 부분 탐색하여 1 반복

3. mid < target 인 경우 집합의 오른쪽 1/2 부분 탐색하여 1 반복

1. C++ (성공 코드 포함)

코드

int binarySearch(int *arr, int arr_sz, int target) {
    int left = 0;
    int right = arr_sz - 1;
    while(left <= right) {
        int mid = (left + right) / 2;

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

하지만 순위 검색 문제를 풀 때는 일치하지 않더라도 target보다 크거나 같은 데이터의 인덱스 값을 구해야했다. --> Lower bound (하한선) algorithm

Lower Bound Binary search

원리는 비슷하나,

target이 mid의 값과 같은 경우 return 하지 않고 해당 인덱스를 right(high)로 변경한 후 다시 이진 탐색을 진행한다.

int lowerBoundBinarySearch(int *arr, int arr_sz, int target) {
    int low = 0;
    int high = arr_sz;
    while(low < high) {
        int mid = (low + high) / 2;

        if (arr[mid] >= target) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
    return low;
}

메인 함수 포함 전체 코드

#include <iostream>

using namespace std;

int binarySearch(int *arr, int arr_sz, int target);
int lowerBoundBinarySearch(int *arr, int arr_sz, int target);
int main() {
    int array[10] = {1, 2, 2, 3, 3, 3, 4, 5, 7, 7};

    cout << "binary search for target 7" << endl;
    int ret = binarySearch(array, 10, 7);
    cout << ret << endl;
    cout << "binary search for target 6" << endl;
    cout << binarySearch(array, 10, 6) << endl;
    cout << "==========================" << endl;
    cout << "lower bound binary search for target 7" << endl;
    cout << lowerBoundBinarySearch(array, 10, 7)<< endl;
    cout << "lower bound binary search for target 6" << endl;
    cout << lowerBoundBinarySearch(array, 10, 6) << endl;
}

int binarySearch(int *arr, int arr_sz, int target) {
    int left = 0;
    int right = arr_sz - 1;
    while(left <= right) {
        int mid = (left + right) / 2;

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

int lowerBoundBinarySearch(int *arr, int arr_sz, int target) {
    int low = 0;
    int high = arr_sz;
    while(low < high) {
        int mid = (low + high) / 2;

        if (arr[mid] >= target) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
    return low;
}

배열 { 1, 2, 2, 3, 3, 3, 4, 5, 7, 7 } 에 대한 이진 탐색 결과:

2. JAVA(효율 0 --> 문제 해결 O)

구현한 로직:

• info에 대해 '-'를 추가한 모든 경우의 수를 만들어 해쉬테이블에 넣는다.
• query를 불러와 데이터를 파싱한 후 해쉬테이블에 key로써 접근하여 score데이터를 가져온다.
• score데이터를 이진탐색을 사용하여 기준이상의 데이터의 개수를 센다.(lower bound 사용)
• 순서대로 값을 반환한다.

했는데도 효율성 0

이었던 이유는..

LinkedList 에 점수를 저장해서이다. ArrayList 로 바꾸니 해결되었다.

문제의 코드:

import java.util.LinkedList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Collections;

class Solution {
    static HashMap<String, List<Integer>> m = new HashMap<>();

    static int binarySearch(int score, String str) {
        int ret = 0;
        List<Integer> values = m.get(str);
        int size = values.size();
        int right = size - 1;
        int left = 0;
        int mid = 0;
        while(left <= right) {
            mid = (right + left) / 2;
            if (score <= values.get(mid)) { // score <= values.get(mid)
                right = mid - 1;
            }
            else { // score > values.get(mid)
                left = mid + 1;
            }
        }
        return size - left;
    }

    void dfs(String[] token, int lv, String str) {

        if (lv == 4) {
            if (m.containsKey(str)) {
                m.get(str).add(Integer.parseInt(token[4]));
            }
            else {
                List<Integer> list = new LinkedList<>();
                list.add(Integer.parseInt(token[4]));
                m.put(str, list);
            }
            return;
        }

        dfs(token, lv+1,str.concat(token[lv]));
        dfs(token, lv+1, str.concat("-"));
    }

    public int[] solution(String[] info, String[] query) {
        int qSize = query.length;
        int[] answer = new int[qSize];

        for (String str: info) {
            String[] token = str.split("\\s");

            List<String> keys = new LinkedList<>();
            dfs(token, 0, "");
        }

        int i=-1;
        HashSet<String> sorted = new HashSet<>();
        for (String quer: query) {
            i++;
            quer = quer.replace(" and ", "");
            String[] token = quer.split("\\s");

            int score = Integer.parseInt(token[1]);
            String m_key = token[0];
            List<Integer> values = m.get(m_key);
            if (values == null) {
                answer[i] = 0;
                continue;
            }

            if (!sorted.contains(m_key)) {
                Collections.sort(values);
                sorted.add(m_key);
            }

            answer[i] = binarySearch(score, m_key);
        }
        return answer;
    }
}

해결 후 : 

LinkedList -> ArrayList

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Collections;

class Solution {
    static HashMap<String, List<Integer>> m = new HashMap<>();

    // answer[i] = binarySearch(0, values.size(), score, values);
    static int binarySearch(int score, String str) {
        int ret = 0;
        List<Integer> values = m.get(str);
        int size = values.size();
        int right = size - 1;
        int left = 0;
        int mid = 0;
        while(left <= right) {
            mid = (right + left) / 2;
            if (score <= values.get(mid)) { // score <= values.get(mid)
                right = mid - 1;
            }
            else { // score > values.get(mid)
                left = mid + 1;
            }
        }
        return size - left;
    }

    void dfs(String[] token, int lv, String str) {

        if (lv == 4) {
            if (m.containsKey(str)) {
                m.get(str).add(Integer.parseInt(token[4]));
            }
            else {
                List<Integer> list = new ArrayList<>();
                list.add(Integer.parseInt(token[4]));
                m.put(str, list);
            }
            return;
        }

        dfs(token, lv+1,str.concat(token[lv]));
        dfs(token, lv+1, str.concat("-"));
    }

    public int[] solution(String[] info, String[] query) {
        int qSize = query.length;
        int[] answer = new int[qSize];

        for (String str: info) {
            String[] token = str.split("\\s");

            List<String> keys = new ArrayList<>();
            dfs(token, 0, "");
        }

        int i=-1;
        HashSet<String> sorted = new HashSet<>();
        for (String quer: query) {
            i++;
            quer = quer.replace(" and ", "");
            String[] token = quer.split("\\s");

            int score = Integer.parseInt(token[1]);
            String m_key = token[0];
            List<Integer> values = m.get(m_key);
            if (values == null) {
                answer[i] = 0;
                continue;
            }

            if (!sorted.contains(m_key)) {
                Collections.sort(values);
                sorted.add(m_key);
            }

            answer[i] = binarySearch(score, m_key);
        }
        return answer;
    }
}