백준 알고리즘 풀이 10815번 - 숫자 카드

 

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

10815번: 숫자 카드

10815번

 

- 이진 탐색 문제.

 

- 알고리즘 -

1. 숫자카드 n개와 숫자카드 m개를 배열로 입력받는다.

2. n배열을 정렬한다. 

3. m만큼 반복문을 돌면서 이분 탐색을 실행해서 있는지 없는지를 찾아낸다.

-시간 복잡도-

이분 탐색 시간복잡도 = log(n)

m만큼 반복문을 돌면서 이분 탐색을 처리하므로 총 시간 복잡도 = mlog(n).

 

처음에는 for문을 두 개 돌려서 해결하려고 했으나, 최악의 경우 50만 * 50만 = 2500억이므로 시간 초과가 뜬다. 이분 탐색으로 문제를 풀어주면 최악의 경우 50만 * log(50만) = 250만 * 0.69897000433 <1억 

따라서 2초 안에 풀 수 있다.

 

-소스 코드-

#include <iostream>
#include <algorithm>
 
int b;
int first_right;
const int left=0;
using namespace std;
 
int first[500001];
int second[500001];
int find(int num,int left,int right)
{
    while(left<=right){
        int mid=(left+right)/2;
        if(first[mid]>num){
            right=mid-1;            
        }
        else if(first[mid]==num){
            return 1;
        }
        else{
            left=mid+1;
        }
    }
    return 0;
}
int main() 
{
    cin>>first_right;
    for(int i=0;i<first_right;i++){
        cin>>first[i];
    }
    sort(first,first+first_right);
    cin>>b;
    for(int i=0;i<b;i++){
        cin>>second[i];
    }
    for(int i=0;i<b;i++){
        cout<<find(second[i],0,first_right-1)<<" ";
    }
    return 0;
}

 

ac!

성공

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)