글 읽기 - 불필요한 부분을 알고자합니다.

akqjqcjs7 3년 전 0

문제는 해결 했지만 시간도 남들에 비해 오래걸렸고 코드도 개념을 이해하고

만들어 작성했지만 코드가 어색하다고 해야하나 그런 느낌이 듭니다.

이 코드에 불필요한 부분이나 개선이 필요한 부분을 알고 싶습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<memory.h>
int compare(const void *a, const void *b) {
    int A = *(int*)a;
    int B = *(int*)b;

    if (A > B) return 1;
    if (A < B) return -1;
    return 0;
}
typedef struct Num {
    int no;
}M;
int lower_bound(int *arr, int s, int e, int data) {
    int m = (s + e) / 2;
    if (arr[e] < data || arr[s] > data) {
        return 0;
    }
    while (s < e) {
        if (arr[m] < data) {
            s = m + 1;
        }
        else {
            e = m; // 여기 안에 들어왔다는건 arr[m]이 데이터보다 크거나 같기 때문
        }
        m = (s + e) / 2;
    }

    if (arr[e] == data) {
        return e;
    }
    else {
        return 0;
    }
}
int upper_bound(int* arr, int s, int e, int data) {
    int m = (s + e) / 2;
    while (s < e) {
        if (arr[m] <= data) {
            s = m + 1;
        }
        else {
            e = m;
        }
        m = (s + e) / 2;
    }
    if (arr[e - 1] == data) {
        return e;
    }
    else {
        return 0;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    qsort(arr, n, sizeof(int), compare);
    int m;
    scanf("%d", &m);
    M *mm = (M*)malloc(sizeof(M) * m);
    for (int i = 0; i < m; i++) {
        int data;
        scanf("%d", &data);
        mm[i].no = upper_bound(arr, 0, n, data) - lower_bound(arr, 0, n - 1, data);
        
    }

    for (int i = 0; i < m; i++) {
        printf("%d ", mm[i].no);
    }
    return 0;
}

pichulia 3년 전 0

400ms면 적당한 속도입니다. 100ms 미만인게 이상한겁니다.

굳이 따지자면 qsort 함수가 O(n log n)을 보장하지 않는다는 점이 신경쓰입니다.

akqjqcjs7 3년 전 0

제가 쓴 qsort가 신경쓰이신다는건가요?

그리고 제가 upper는 0부터n을 lower는 0부터 n-1을 이용했습니다. 구글링을 통해 배운거는

0부터 n까지 이용했습니다. 하지만 저는 lower는 n까지 할 필요가없다 생각했고 upper는 필요하다 판단해 n까지 했는데 맞는 판단일까요?

pichulia 3년 전 0

일반적인 lower_bound라면 arr[n-1] < data 인 경우 n을 return해야하기 때문에 0부터 n까지 보는게 좋긴 합니다만.. 이 문제의 경우는 아무래도 상관없으니... 정답을 받았다면 상관없습니다.

그리고 qsort는 기본적으로 quick sort 알고리즘을 기반으로 동작하는데.. 퀵소트는 그냥 n^2이라고 생각하시는게 속편합니다.

뭐 컴파일러가 이것저것 최적화를 했다곤 하지만 어찌됐든 공식적으로 O(n log n)을 보장하지 않는다고 했기 때문에 지양해야합니다.

akqjqcjs7 3년 전 0

친절한 답변 감사드립니다!

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

문제

문제

출처

ICPC

불필요한 부분을 알고자합니다.

akqjqcjs7 3년 전 0

pichulia 3년 전 0

akqjqcjs7 3년 전 0

pichulia 3년 전 0

akqjqcjs7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말