[BOJ 1920] std::binary_search()를 set에 사용하면 안되는 이유 (이분탐색이 O(n)이 되어버리는 매직)

블로그 글 쓰는게 정말 오랜만인 것 같네요..!

교환학생 당시에 열심히 블로그 쓰려했지만 너무 많은 여행과 일정으로 잠시 블로그를 접었어요. 교환학생 이야기는 틈나면 다시 작성해보겠습니다.

 

 한국 돌아와서 소마(소프트웨어 마에스트로)에 도전하고자 열심히 알고리즘 공부를 하던 도중 재밌는 사실을 발견해서 기록하고자 블로그를 작성하게 되었습니다. 

---

이분 탐색 기본 문제를 풀이하던 도중, 정렬이 자동으로 되는 set을 사용해서 이 문제를 풀었습니다. 

 

이분 탐색을 공부하고자 해당 문제를 풀었으니 std::binary_search()를 사용했더니 세상에 시간초과가 났습니다.

 

<문제의 코드>

 

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n; //배열 크기
set<int> s; 
int m;

void input(){
    int cinn;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        cin>>cinn;
        s.insert(cinn);
    }
    cin>>m;
}

void solve(){
    int test;
    for (int i = 0; i < m; i++)
    {
        cin>>test;
        
        //이 부분!!!!!!!!!
        cout<<binary_search(s.begin(),s.end(),test)<<"\n";
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solve();
}

 

---

std::binary_search()를 set에 사용하면 안되는 이유

= set은 포인터로 연결된 트리 구조이므로 배열처럼 바로 중간에 접근하지 못하기 때문

C++ 에서 binary_search()의 작동 방식을 보면 처음에 시작 이터레이터와 끝 이터레이터를 받아서 중간을 찾습니다. 이분탐색 특성 상 처음에 바로 중간 mid=(start+end)/2 으로 가야합니다. 배열의 경우 바로 인덱스로 접근이 가능하지만, set은 한 번에 접근이 불가능합니다. 배열은 랜덤엑세스가 가능하지만 set은 불가능합니다.

 

그 이유는 set이 배열의 구조가 아닌 포인터로 연결된 트리의 구조이기 때문입니다. 포인터로 된 set은 처음부터 mid까지 간 다음 비교하기 때문에 시간 복잡도가 O(n)이 나옵니다. 

 

 그래서 cpp는 set 자체적으로 메서드를 가지게끔해서 이 문제를 해결했습니다. 따라서 std::binary_search()가 아닌, set의 내장함수를 사용해야합니다.

 

참고 : https://codeforces.com/blog/entry/17347

find() vs lower_bound() - Codeforces

 

---

해결방법

1. set의 내장함수 find, lower_bound, upper_bound, count 중에서 자신이 원하는 함수를 사용하자!

2. 배열로 구현한 다음 sort()를 이용해서 정렬하고 std::binary_search()를 활용하자!

 

<통과된 코드>

set의 내장함수 find 사용

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n; //배열 크기
set<int> s;
int m;

void input(){
    int cinn;
    cin>>n;
    for (int i = 0; i < n; i++)
    {
        cin>>cinn;
        s.insert(cinn);
    }
    cin>>m;
}

void solve(){
    int test;
    for (int i = 0; i < m; i++)
    {
        cin>>test;
        cout<<(s.find(test)!=s.end())<<"\n";
    }   
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();

    solve();
}