글 읽기 - c++ 도와주세요 ㅠㅠㅠ

kimsan 2년 전 0

upper bound, lower bound 쓰지 않고 이 방식으로 클래스 만들어서 count 세는 이분 탐색 방식은

시간 초과가 납니다... 이유가 뭘까요?? 똑같이 O(nlogn)이라 생각하는데 말이죠..

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <stack>
using namespace std;

class myNum {
public:
    int num;
    int count;

    myNum(int num) {
        this->num = num;
        this->count = 1;
    }
    void add() {
        this->count += 1;
    }
};

int find(int begin, int end, int target, vector<myNum> data) {
    if (end - begin <= 1) {
        if (data[begin].num == target) {
            return data[begin].count;
        }
        else if (data[end].num == target) {
            return data[end].count;
        }
        else {
            return 0;
        }
    }
    int middle = (begin + end) / 2;
    if (data[middle].num == target) {
        return data[middle].count;
    }
    else if (data[middle].num < target) {
        begin = middle + 1;
    }
    else {
        end = middle - 1;
    }
    return find(begin, end, target, data);
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int x, y, tmp;
    vector<int> data1, data2;
    cin >> x;
    for (int i = 0; i < x; i++) {
        cin >> tmp;
        data1.push_back(tmp);
    }
    cin >> y;
    for (int i = 0; i < y; i++) {
        cin >> tmp;
        data2.push_back(tmp);
    }
    sort(data1.begin(), data1.end());
    vector<myNum> my_data;
    my_data.push_back(myNum(data1[0]));
    for (int i = 1; i < x; i++) {
        if (my_data[my_data.size() - 1].num == data1[i]) {
            my_data[my_data.size() - 1].add();
        }
        else {
            my_data.push_back(myNum(data1[i]));
        }
    }
    for (int i = 0; i < y; i++) {
        cout << find(0, my_data.size() - 1, data2[i], my_data) << "\n";
    }
    return 0;
}

djm03178 2년 전 2

data를 참조형으로 만들어주면 통과됩니다.

지금은 vector 전체를 값으로 넘기고 있기 때문에, 재귀호출 시마다 data의 내용이 전부 복사되어 새로운 vector가 만들어지므로 O(NMlogN)의 시간이 걸리게 됩니다.

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

문제

문제

출처

ICPC

c++ 도와주세요 ㅠㅠㅠ

kimsan 2년 전 0

djm03178 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말