글 읽기 - 시간초과 문제 nlogn으로 풀리는 코드

ksgkms23 5년 전 0

우선 제 코드입니다.

nlogn의 시간복잡도로 풀린다고 생각합니다.

lower_bound 가 이분 탐색으로 logN이 걸리고

for문으로 모든 n번 돌고있습니다.

입력값이 100,000 이고 이는 1초안에 충분히 들어와야한다고 생각이 드는데 시간초과가 뜹니다.
혹시 입력값의 범위가 100,000가 아닌가 해서 질문드립니다
혹은 제 코드가 잘못되었거나, 잘못알고있는 부분에 대한 지적을 해주시면 감사하겠습니다.

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
vector<long> k;
int main(void){
    int a;
    cin >> a;
    while(a--){
        long b;
        cin >> b;
        k.push_back(b);
    }
    long answer = 99999999;

    long o = 0;
    for(int i=0; i<k.size(); i++){
        vector<long> y;
        y.assign(k.begin(),k.end());
        y.erase(y.begin()+i); //자기자신은 이분탐색에서 제외하기 위해
        auto q = lower_bound(y.begin(), y.end()-1, -k[i]); // 0을 만들어주는 -k[i]를 찾고 없을 시 가까운값 구함
        if(q-y.begin()+1<y.size()){
            if(abs(k[i]+y[q-y.begin()])==min(abs(k[i]+y[q-y.begin()]),abs(k[i]+y[q-y.begin()+1]))){
                o = k[i]+y[q-y.begin()];
            }
            else{
                o = k[i]+y[q-y.begin()+1];
            }
        }
        else{
            o = k[i]+y[q-y.begin()];
        }
        if(abs(answer)==min(abs(answer), abs(o))){
            answer = answer;
        }
        else{
            answer = o;
        }
        
    }
    cout << answer;
}

djm03178 5년 전 1

두 문장이 O(N)이기 때문에 총합 O(N^2)입니다.

21번째 줄, assign은 말 그대로 모든 원소를 하나씩 복사해 와서 대입합니다. 당연히 원소 수가 n개면, O(n)의 시간이 걸립니다.
22번째 줄, erase는 원하는 위치의 원소를 지운 뒤, 그 뒤쪽에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨옵니다. 평균 / 최대 O(n)개의 원소를 옮겨야 하므로 역시 O(n) 시간이 걸립니다. (다만 이 함수는 memmove를 내부적으로 사용하기 때문에 매우 빠르긴 합니다.)

ksgkms23 5년 전 0

assign, erase에 대한 복잡도를 모르고 그냥 쓰고 있었내요 감사합니다.

벡터를 또 할당하는 짓을 안하고 그냥 처음 벡터만 이용해서 인덱스만 바꾸는식으로 유사하게 푸니까 시간초과안뜨고 풀게되었습니다! ^^

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

문제

문제

출처

ICPC

시간초과 문제 nlogn으로 풀리는 코드

ksgkms23 5년 전 0

djm03178 5년 전 1

ksgkms23 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말