10816번 - 97% 시간 초과(해결)

10816번 - 숫자 카드 2

##################다시 풀기##################

일단 이분 탐색 방법에서 찾은 후에,  왼쪽을 다시 이분탐색, 오른쪽을 이분탐색 하는 방식.

아직 이 문제는 제대로 못 품 ( 97% 시간 초과 ) ... 이유를 모르겠음...

나도 어떤 분 코드를 보고 참조하였음. 

근데 그 분 코드도 내가 그대로 돌려보니 시간초과가 발생...

문제점

1. vector 로 구현하다가 느리다고 하여 배열로 바꿨지만 여전히 시간 초과..

2. cin, cout 전부 printf, sacnf 로 바꿨지만 시간 초과.

==> 문제점 해결

입력으로 가지고 있는 카드가 50 50 50 50 50 이렇게 max 로 들어오고 확인해야 할 카드 또한 50 50 50 50 이런식으로 입력이 들어온

다면 중복된 계산이 엄청나게 많이 필요한 경우가 있다.

그래서 한번 확인한 카드는 다시 확인할 필요없이 값을 출력하도록 check 라는 배열을 만들었다.

그래서 다음에는 계산 안하고 캐시처럼 이용해서 바로 출력하도록 하니 통과했다.

cin, cout , vector 의 문제가 아니었다.

 배운점

- 이분 탐색 코드 형태를 바꿀 수 있게 되었다. 

종만북에서는 lo=mid, hi=mid 이런 형태로 바꾸는 식이었는데 문제를 풀다보니 나한테는 약간 헷갈림과 이해 없이 쓰는 찜찜함이 생겼다.

이분탐색 문제는 계속 그렇게 풀어왔고

이번에 구글링하면서 이분탐색 공부하면서 

그냥 low , high 값에 어떤 초기값을 넣고, low, high 값을 어떤식으로 변화시킬지 확실히 알 수 있게 됐다.

또, 이분 탐색에서 for문을 100번 돌리는 방법 뿐만 아니라, if, while 문으로 변환할 수 있는 방식도 터득하게 됐다. 개이득!!

<틀린 코드 97%에서 시간 초과>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int have[500001];
int toCompare[500001];
 
int binarySearch(int lo, int hi,int key)
{
    int result = 0;
    if (lo<=hi)
    {
        int mid = (lo + hi) / 2;
        if (have[mid] == key)
        {
            result += binarySearch(lo, mid - 1, key);
            result += binarySearch(mid + 1, hi, key);
            result += 1;
        }
        else if (have[mid] <  key)
        {
            result +=binarySearch(mid+1, hi, key);
        }
        else if (have[mid] >  key)
        {
            result +=binarySearch(lo, mid-1, key);
        }
        
        return result;
    }
    else
    {
        return 0;
    }
 
    
}
int main()
{
    int N, M;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d",&have[i]);
    }
    scanf("%d",&M);
    for (int j = 0; j < M; j++)
    {
        scanf("%d", &toCompare[j]);
    }
 
    sort(have, have+N);
 
    for (int i = 0; i < M; i++)
    {
        int lo = 0;
        int hi = N -1 ;
        int key = toCompare[i];
    
        printf("%d ", binarySearch(0, hi, key));
        //cout << binarySearch(0, hi, key) << " ";
        
    }
 
    return 0;
}

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
vector<int> have;
vector<int> toCompare;
int check[20000001];
int binarySearch(int lo, int hi, int key)
{
    int result = 0;
    if (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (have[mid] == key)
        {
            result += binarySearch(lo, mid - 1, key);
            result += binarySearch(mid + 1, hi, key);
            result += 1;
        }
        else if (have[mid] <  key)
        {
            result += binarySearch(mid + 1, hi, key);
        }
        else if (have[mid] >  key)
        {
            result += binarySearch(lo, mid - 1, key);
        }
 
        return result;
    }
    else
    {
        return 0;
    }
 
 
}
int main()
{
    int N, M;
    //freopen("input.txt", "r", stdin);
    cin >> N;
    memset(check, -1, sizeof(check));
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        have.push_back(tmp);
    }
    cin >> M;
    for (int j = 0; j < M; j++)
    {
        int tmp;
        cin >> tmp;
        toCompare.push_back(tmp);
    }
 
    sort(have.begin(), have.end());
 
    for (int i = 0; i < toCompare.size(); i++)
    {
        int lo = 0;
        int hi = have.size() - 1;
        int key = toCompare[i];
 
        if (check[key + 10000000] == -1)
        {
            check[key + 10000000] = binarySearch(lo, hi, key);
            cout << check[key + 10000000] << " ";
 
        }
        else
        {
            cout << check[key + 10000000] << " ";
        }
        
 
    }
    cout << endl;
    return 0;
}