글 읽기 - 시간초과

dwhylee 7년 전 0

데이터 추가된 이후에 시간 초과 뜨길래 예전에 수정하려고 했던 부분 (아래 소스) 을 수정해서 올렸는데

96% 데이터에서 시간초과가 나더라구요..

수정 내용은 작은 것과 큰것을 전에는 다 그냥 체크해서 쓸모없는 시간 낭비가 있었는데, 그걸 줄인건데

해도 시간 초과가 나는걸 보면 아마.. N 번을 여러번 도는 예제가 추가된 것 같습니다.??

(N 이랑 N/2 N/2 .. 이렇게 생각해보면 N*? 번 돌꺼 같은데) 아니면 같은 번호를 가진 카드가 여러장 있는 경우도 있는지 ??..

다른 수정해야할 부분 있을까요?

함수로 짰다가 while 로도 해봤지만 똑같더라구요.

    int index = (start + end) / 2;
	if (start > end)										return 0;
	if (cardList[index] == compareNum){
		for (int i = start; i<=end; i++){
			if (cardList[i] == compareNum) 			returnValue++;
		}
		return returnValue;
	}
	else if (cardList[index] > compareNum)		binarySearch(start, index - 1);
	else                                                   binarySearch(index + 1, end);

위 소스에서 아래 소스

	int index = (start + end) / 2;
	if (start > end)										return 0;
	if (cardList[index] == compareNum){
		int tmp = index;							 
		while(tmp >= start){						// 숫자 작은것과 큰것 제외시키면  시간 줄일 수 있음. 0번 부터 N-1 번까지 >> N번 :  n^2 줄일수 있음
			if (cardList[tmp--] < compareNum) break;
			returnValue++;
		}
		tmp = index;
		while (tmp <= end){
			if (cardList[tmp++] > compareNum) break;
			returnValue++;
		}
		return returnValue;
	}
	else if (cardList[index] > compareNum)		binarySearch(start, index - 1);
	else                                        binarySearch(index + 1, end);


ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ전체소스 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int number;
int condition;
int compareNum;
int returnValue;
int cardList[500001] = { 0 };

int main(){
	scanf("%d", &number);
	for (int i = 0; i < number; i++){
		scanf("%d", &cardList[i]);
	}
	sort(cardList, cardList + number);				// NlogN
	scanf("%d", &condition);							
	for (int i = 0; i < condition; i++){				// MlongN
		scanf("%d", &compareNum);
		returnValue = 0;
		int start = 0, end = number -1;
		while (1){
			int index = (start + end) / 2;
			if (start > end)										break;
			if (cardList[index] == compareNum){
				int tmp = index;
				while (tmp >= start){						// 숫자 작은것과 큰것 제외시키면  시간 줄일 수 있음. 0번 부터 N-1 번까지 >> N번 :  n^2 줄일수 있음
					if (cardList[tmp--] < compareNum) break;
					returnValue++;
				}
				tmp = index;
				while (tmp <= end){
					if (cardList[tmp++] > compareNum) break;
					returnValue++;
				}
				returnValue--;
				break;
			}
			else if (cardList[index] > compareNum)		end = index - 1;
			else                                       start = index + 1;
		}
		printf("%d ", returnValue);
	}
}

x21999 7년 전 0

M을 입력받은 후 입력받은 수에 대하여 전부다 똑같은 자료가 들어있는 수가 있을 경우 기존의 하셨던 N을 logN로 바꾸어서 하시면 좀 더 빨라질것 같습니다.

dwhylee 7년 전 0

같은 자료가 추가된 건지.. 문제에는 그런 조건이 없긴 한데 카드라는 개념을 봐서는 ㅎㅎ.. 일단 수정해볼께요.

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

문제

문제

출처

ICPC

시간초과

dwhylee 7년 전 0

x21999 7년 전 0

dwhylee 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말