글 읽기 - 10815숫자카드 시간초과 질문입니다 ㅠㅠ

wccho89 6년 전 0

cin을 쓰면 시간초과된다고 하여 모두 scanf랑 printf로 바꿨는데도..

시간초과가 계속 뜨네요...

이유를 모르겠습니다 ㅠㅠ

#include <iostream>
#include <stdio.h>

using namespace std;

int BinarySearch(int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1, mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (dataArr[mid] > findData) high = mid - 1;
        else if (dataArr[mid] < findData) low = mid + 1;
        else return mid;
    }
    return -1;
}

void selectionsort(int* arr, int n){
	int temp;
	for(int i=0;i<n-1;i++){
		for(int j=i+1; j<n;j++){
			if(arr[i]>arr[j]){
				temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		}
	}
}

int main(){
	int N;
	scanf("%d",&N);

	int *card = new int[N];

	for(int i=0;i<N;i++){
		scanf("%d",&card[i]);
	}

	int M;
	scanf("%d",&M);

	int *num = new int[M];

	for(int j=0;j<M;j++){
		scanf("%d",&num[j]);
	}

	selectionsort(card, N);

	for(int k=0;k<M;k++){
		if(BinarySearch(card, N, num[k])==-1)
			printf("0");
		else
			printf("1");

		printf(" ");
	}

	printf("\n");

	delete []card;
	return 0;
}

sgchoi5 6년 전 2

1) cin 을 쓰면 안 된다

=> 요거 한 번 읽어 보세요. http://gooddaytocode.blogspot....

cin/cout 는 입출력 회수가 작은 경우에 써도 됩니다. 입출력 회수가 많아지면 문제인 것 이고요.

2) 이분탐색은 입력값이 정렬이 되어야 하는데, 이 정렬 방법이 문제네요

이분탐색의 복잡도는 O(logN) 인데, 정렬 방식이 O(N²) 이네요.

정렬 방식을 quick sort 나 merge sort 같은 O(NlogN) 시간복잡도를 가진

알고리즘으로 변경하셔야 합니다.

이분탐색: O(logN) 에서 N 이 500,000 이면 대략 18

정렬1: O(N²) 500,000 * 500,000 = 250,000,000,000 = 2천5백억이네요.

정렬2: O(NlogN) 500,000 * 10 = 9,000,000 = 9 백만이네요.

3) 공간 복잡도를 생각하면 이 문제는 정렬 안 해도 됩니다.

입력값의 모든 범위인 2 천만개 숫자를 의 int array 를 잡으면 76MB 면 됩니다. bool 로 하면 1/4 이겠네요.

wccho89 6년 전 0

좋은 답변 감사합니다 ^^

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

문제

문제

출처

ICPC

10815숫자카드 시간초과 질문입니다 ㅠㅠ

wccho89 6년 전 0

sgchoi5 6년 전 2

wccho89 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말