글 읽기 - sorting 하고 하는게 빠른건가요..

chso2 8년 전 0

2진탐색이라 그냥 짜봤는데....시간초과가 뜨네요

틀린부분이 있으면 뭔지 모르겠고....

정렬하고 탐색하면 탐색은 빠르겠지만 정렬하는데 시간까먹는거 같아서....생략했는데 그게 더 빠른건가요?

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
/*
    첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 
    둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 
    숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
 
    셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 
    넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 숫자가 주어지며, 
    이 숫자는 공백으로 구분되어져 있다. 
    이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
*/
int N;
int M;
int check;
int cnt;
int i;
int temp;
vector <int>card;
 
int binary_search(int n, int start, int end){
    int mid = (start + end) / 2;
    if (end - start <= 1){
        cnt++;
        return 0;
    }else{
        for (int j = start; j < mid; j++){
            if (card[j] == n){
                binary_search(n, start, mid);
                break;
            }
        }
        for (int k = mid; k < end; k++){
            if (card[k] == n){
                binary_search(n, mid, end);
                break;
            }
        }
    }
    return 0;
}
int main(){
    cin >> N;
    for (i = 0; i < N; i++){
        cin >> temp;
        card.push_back(temp);
    }
    cin >> M;
    for (i = 0; i < M; i++){
        cnt = 0;
        cin >> check;
        binary_search(check, 0, N);
        cout << cnt << " ";
    }
}

hj_d 8년 전 0

이진탐색 개념을 다시 공부 해보셔야 할거 같아요...ㅜㅜ 정렬 안한 상태로 이진 탐색은 아무 의미 없어요

hokma 8년 전 0

이진탐색은 보통 mid값과 비교해서 범위를 반토막 내기 때문에 정렬이 필요합니다.

위의 소스는 내부를 다 돌아서 찾는거라 정렬이 필요 없을거 같기도 한데 저렇게 풀면 이진탐색이 아닌것 같습니다 ㅠ

dtc03012 8년 전 0

그리고 cin , cout 은 시간이 많이 걸리므로 scanf , printf를 사용하도록 해보세요

vector 도 시간이 많이걸리므로 그냥 배열을 사용하세요

dtc03012 8년 전 0

그리고 정렬도 안하고 바이너리 서치..

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

문제

문제

출처

ICPC

sorting 하고 하는게 빠른건가요..

chso2 8년 전 0

hj_d 8년 전 0

hokma 8년 전 0

dtc03012 8년 전 0

dtc03012 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말