글 읽기 - 이진 탐색 트리 어디서 실수하고있나요?.....

s7d8f9 6년 전 0

제가 느끼기는 이진탐색으로 찾아서 시간초과가 안날꺼같은데 ... 계속 시간초과가 나오는데 이유를 알 수 있을까요?...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 300005
#define INF 987654321
#define MOD 1000000
typedef long long ll;
#pragma warning(disable:4996)
using namespace std;

int n,num;
long long total;
bool tf[MAX][2];
deque<pair<int, int>> dq;


int find(int st,int mi,int fi)
{
    if(num<dq.at(st).first)
    {
        int tmp=dq.at(st).second+1;
        tf[dq.at(st).first][0]=true;
        dq.push_front(make_pair(num,tmp));
        return tmp;
    }
    if(dq.at(fi).first<num)
    {
        int tmp=dq.at(fi).second+1;
        tf[dq.at(fi).first][1]=true;
        dq.push_back(make_pair(num, tmp));
        return tmp;
    }
    while(1)
    {
        int tmp;
        if(abs(st-fi)<=1)
        {
            if(tf[dq.at(fi).first][0]==false)
            {
                tmp=dq.at(fi).second+1;
                dq.insert(dq.begin()+fi, make_pair(num,tmp));
            }
            else if(tf[dq.at(st).first][1]==false)
            {
                tmp=dq.at(st).second+1;
                dq.insert(dq.begin()+fi, make_pair(num,tmp));
            }
            return tmp;
        }
        if(num<dq.at(mi).first)
        {
            fi=mi;
            mi=(st+fi)/2;
        }
        else if(dq.at(mi).first<num)
        {
            st=mi;
            mi=(st+fi)/2;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    //n=300000;
    scanf("%d",&num);
    //num=1;
    dq.push_back(make_pair(num, 0));
    printf("0\n");
    
    for(int i=1;i<n;i++)
    {
        int a=0,c=dq.size()-1,b=(a+c)/2;
        scanf("%d",&num);
        //num=i;
        total+=find(a,b,c);
        printf("%lld\n",total);
    }
    return 0;
}

solveit 6년 전 1

insert는 최악의 경우 O(n) 입니다.

djm03178 6년 전 1

deque이 내부적으로 배열 형태로 구현되어 있기 때문에 그렇습니다. 만일 링크드 리스트였다면, 반대로 at이 O(n)이 걸릴 것입니다. 그래서 "원하는 위치를 찾는" 것과 "그 위치에 새로운 원소를 삽입하는 것"을 동시에 O(1)을 만족하게 만들기는 어렵습니다.

s7d8f9 6년 전 0

그럼 제가 생각한 방향으로는 풀기 힘들다는 의미인가요?..... 다른방식을 생각해보아야 하나요?

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

문제

문제

출처

ICPC

이진 탐색 트리 어디서 실수하고있나요?.....

s7d8f9 6년 전 0

solveit 6년 전 1

djm03178 6년 전 1

s7d8f9 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말