글 읽기 - 시간초과 오류

dntjd292 2년 전 1

이진탐색을 구현하여 풀어봤는데... 시간초과가 발생하네요....

어떤 부분이 문제 일까요..ㅜㅜ

미흡한 제가 보기엔 시간복잡도 O(N * log N)인데 말이죠...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 오름차순 정리(중복 제거)
// 좌표 압축 인덱스 부여 
// 기존 배열과 비교 후 인덱스 값 입력 
// index : 압축좌표 k : 기존 좌표 begin : 압축좌표의 앞단 end : 압축 좌표의 뒷단
int BinarySearch(vector<int> index,int k ,int begin ,int end)
{
    if(begin > end) return - 1;
    int m = (begin + end) / 2;
    if(index[m] == k) return m;
    else if(index[m] > k) return BinarySearch(index, k, begin, m-1);
    else return BinarySearch(index, k, m+1, end);
}

int main()
{
    int num, temp;
    vector<int> index;
    vector<int> x_list;
    // 값 입력 
    scanf("%d", &num);
    for(int i=0; i < num; i++)
    {
        scanf("%d", &temp);
        index.push_back(temp);
        x_list.push_back(temp);
    }
    // 오름차순 정렬
    sort(index.begin(), index.end());
    // 중복제거 
    index.erase(unique(index.begin(), index.end()), index.end());
    // index 부여
    for(int i=0; i < x_list.size(); i++)
        x_list[i] = BinarySearch(index, x_list[i], 0, index.size());  
    for(auto el : x_list)
        printf("%d ", el);
    printf("\n");            
}

11번째 줄과 같이 vector를 값으로 받으면 함수가 호출될 때마다 기존 vector의 내용이 전부 복사되어 새로운 vector가 만들어져 전달됩니다. 이분 탐색에는 시간을 O(logN)번만 쓰는데, 함수 호출을 O(logN)번 하면서 매번 O(N)의 벡터가 복사된다면 시간은 이분 탐색 한 번에 O(NlogN)이 되고, 원소가 O(N)개이므로 총 시간 복잡도는 O(N^2logN)이 됩니다.

참조형으로 바꾸면 통과됩니다.

dntjd292 2년 전 0

아.. 함수가 호출되면서 N log N 이 되는군요... 기초가 중요하다는걸 다시한번 알고 갑니다..

앞으론 참조나 포인터도 한번 써 봐야겠네요..ㅎㅎ 답변 감사합니다!

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

문제

문제

출처

ICPC

시간초과 오류

dntjd292 2년 전 1

djm03178 2년 전 0

dntjd292 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말