글 읽기 - 시간초과 문제입니다..

carpediemsh 7년 전 0

시간초과가 어느부분에서 나는걸까요?

이분탐색으로 구현을 하였는데..

sort에서 나는걸까요?

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;

int search(int x, vector<int> v){
    int left = 0;
    int right = n-1;
    int mid;
    
    while(left<=right){
        mid = (left+right)/2;

        if(v[mid] > x){
            right = mid-1;
        }
        else if(v[mid] == x){
            return 1;
        }
        else{
            left = mid+1;
        }
    }
    
    return 0;
}

int main(){
    
    scanf("%d",&n);
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        scanf("%d",&v[i]);
    }
    sort(v.begin(), v.end());
    
    int m;
    scanf("%d",&m);
    for(int i=0; i<m; i++){
        int input;
        scanf("%d",&input);
        if( v[0] <= input && input <= v[n-1]){
            printf("%d\n",search(input, v));
        }
        else{
            printf("%d\n", 0);
        }
        
    }
    
    
    return 0;
}

kdk8361 7년 전 0

right가 n-1이라 그런거 같습니다.

carpediemsh 7년 전 1

정렬된 vector의 인덱스가 0~n-1까지여서 그렇게 설정한것인데

이 부분이 시간초과와 연관이 있나요?

kdk8361 7년 전 0

아 제가 잘못봤네요.

jayceking 7년 전 0

이분탐색 부분에서 존재하지 않는 값을 탐색할때마다 전체를 탐색해서 그런거 같아요

예외처리를 추가해보세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 문제입니다..

carpediemsh 7년 전 0

kdk8361 7년 전 0

carpediemsh 7년 전 1

kdk8361 7년 전 0

jayceking 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말