글 읽기 - 이 풀이가 시간초과나는 이유를 모르겠습니다

dhsg0717 2년 전 0

lower_bound, upper_bound의 차이로 푸는 법을 알기 전에 lower_bound를 구한 뒤,

해당 인덱스부터 개수를 셀 숫자가 몇개 있는지 하나씩 카운트하는 것으로 구현했었는데 시간초과가 나더라구요.

정렬이 O(NlogN)이라면 n이 500,000이더라도 약 10,000,000 정도이고,

m이 500,000일 때, for반복 횟수 500,000에 lower_bound 연산이 약 20이라면 500,000 * 20 = 10,000,000정도이고,

해당 숫자가 몇 개 있는지 카운트하는 총 연산은 n을 넘지 않으니 최대 500,000이라고 생각이 됩니다.

마지막으로 결과를 출력하는 반복횟수도 500,000입니다.

이 정도면 많이 쳐도 1억의 연산과는 거리가 있어서 시간초과가 나지 않을 것 같았는데 어째서 나는걸까요?

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<sstream>
#include<limits>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>

using namespace std;
const int INF = 1987654321;
const int MAX = 101;
const int _MOD = 1000000007;

int n, m;
vector<int> v;
vector<int> v2;
vector<int> ret;

int lower_binary(int target) {
    int start = 0, end = n;

    while(start < end) {
        int mid = (start + end) / 2;
        if(v[mid] >= target)
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

int upper_binary(int target) {
    int start = 0, end = n;

    while(start + 1 < end) {
        int mid = (start + end) / 2;
        if(v[mid] > target)
            end = mid;
        else
            start = mid;
    }
    return start + 1;
}


int main(void)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());

    cin >> m;
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        v2.push_back(temp);
        ret.push_back(0);
    }

    
    for(int i = 0; i < m; i++) {
        int low = (v2[i] == v[0]) ? 0 : lower_binary(v2[i]);
        if(v[low] != v2[i]) continue;
        // 왼쪽 끝부터 해당 수 개수를 하나씩 센다
        while(v[low++] == v2[i]) {
            ret[i]++;
        }
    }

    for(int i = 0; i < m; i++)
        cout << ret[i] << ' ';

    return 0;
}

djm03178 2년 전 1

같은 수에 대해 여러 번 물을 수도 있습니다. 만일 n개가 다 같은 수이고 이 수의 개수를 m번 물으면 총 시간은 O(nm)이 됩니다.

dhsg0717 2년 전 0

아 m이 중복이 될수도 있었군요...이제 납득이 되네요 ㅜㅜ 감사합니다!

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

문제

문제

출처

ICPC

이 풀이가 시간초과나는 이유를 모르겠습니다

dhsg0717 2년 전 0

djm03178 2년 전 1

dhsg0717 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말