글 읽기 - c) 퀵소트와 이진탐색

choyj1127 2년 전 0

두 가지 방법을 사용했으나 시간초과가 나네요ㅜ 이 문제는 어떻게 해결해야할까요?

#include <stdio.h>
#include <stdlib.h>
int arr[500005];
int compare(const void* a, const void* b)
{
    int num1 = *(int*)a;
    int num2 = *(int*)b;
    if (num1 < num2)
        return -1;
    else if (num1 == num2)
        return 0;
    else
        return 1;
}
int binary_allSearch(int arr[], int first, int last, int target, int cnt)
{
    if (first > last) {// 찾지못함 || 모두 탐색끝
        return cnt;
    }
    int mid = (first + last) / 2;
    if (target < arr[mid])
        return binary_allSearch(arr, first, mid - 1, target, cnt);
    else if (arr[mid] < target)
        return binary_allSearch(arr, mid + 1, last, target, cnt);
    else // 탐색됨
    {
        cnt++;
        cnt = binary_allSearch(arr, first, mid - 1, target, cnt); //탐색위치에서 왼쪽탐색
        cnt = binary_allSearch(arr, mid + 1, last, target, cnt); //탐색위치에서 오른쪽탐색
        return cnt;
    }
}

int main() {
    int N; scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    qsort(arr, N,sizeof(int), compare);

    int M; scanf("%d", &M);
    int num; int count = 0; int cnt = 0;
    for (int i = 0; i < M; i++) {
        scanf("%d", &num);
        count = binary_allSearch(arr, 0, N - 1, num, cnt);
        printf("%d ", count);
    }
    return 0;
}

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

문제

문제

출처

ICPC

c) 퀵소트와 이진탐색

choyj1127 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말