글 읽기 - 시간초과가 나는 이유가 뭘까요,,?

timosean 3년 전 0

반복문을 적당히 돌렸다고 생각하는데, 시간초과가 뜨는 이유가 대체 뭘까요...ㅠㅠ

못잡겠습니다

다른 ide로 하면 결과가 빨리빨리 잘 뜨던데

#include <stdio.h>
#include <stdlib.h>

#define MAX_LEN 100010

typedef struct _casher{
	int prodNum;	//상품의 개수(w)
	int memNo;		//회원번호
	int casherNo;	//계산대 번호
}Casher;

typedef Casher Data;

typedef struct _heap{
	int dataNum;
	Data heapArr[MAX_LEN];
}Heap;

void heapInit(Heap * ph){
	ph->dataNum = 0;
}

int isEmpty(Heap * ph){
	if(ph->dataNum==0)
		return 1;
	else
		return 0;
}

int getParentIdx(int idx){
	return idx/2;
}

int getLeftChild(int idx){
	return idx*2;
}

int getRightChild(int idx){
	return idx*2 + 1;
}

int getHighPriChild(Heap* ph, int idx){
	if(getLeftChild(idx) > ph->dataNum)
		return 0;
	
	else if(getLeftChild(idx) == ph->dataNum)
		return getLeftChild(idx);
	
	else{
		if((ph->heapArr[getLeftChild(idx)]).prodNum > (ph->heapArr[getRightChild(idx)]).prodNum)
			return getRightChild(idx);
		
		else
			return getLeftChild(idx);
	}
}

int maxHighPriChild(Heap* ph, int idx){
	if(getLeftChild(idx) > ph->dataNum)
		return 0;
	
	else if(getLeftChild(idx) == ph->dataNum)
		return getLeftChild(idx);
	
	else{
		if((ph->heapArr[getLeftChild(idx)]).casherNo > (ph->heapArr[getRightChild(idx)]).casherNo)
			return getLeftChild(idx);
		
		else
			return getRightChild(idx);
	}
}

void heapInsert(Heap * ph, Data data){
	int idx = ph->dataNum + 1;
	
	while(idx!=1){
		if(data.prodNum < (ph->heapArr[getParentIdx(idx)]).prodNum){	//새로운 데이터가 우선순위가 더 높을경우
			ph->heapArr[idx] = ph->heapArr[getParentIdx(idx)];
			idx = getParentIdx(idx);
		}		
		
		else
			break;
	}
	
	ph->heapArr[idx] = data;
	ph->dataNum += 1;
}

void maxInsert(Heap * ph, Data data){
	int idx = ph->dataNum + 1;
	
	while(idx!=1){
		if(data.casherNo > (ph->heapArr[getParentIdx(idx)]).casherNo){	//새로운 데이터가 우선순위가 더 높을경우
			ph->heapArr[idx] = ph->heapArr[getParentIdx(idx)];
			idx = getParentIdx(idx);
		}		
		
		else
			break;
	}
	
	ph->heapArr[idx] = data;
	ph->dataNum += 1;
}

Data heapDelete(Heap * ph){
	Data rdata = ph->heapArr[1];
	Data lastData = ph->heapArr[ph->dataNum];
	int parentIdx = 1;
	int childIdx;
	
	while(childIdx = getHighPriChild(ph, parentIdx)){
		if(lastData.prodNum < (ph->heapArr[childIdx]).prodNum)
			break;
		
		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}
	
	ph->heapArr[parentIdx] = lastData;
	ph->dataNum -= 1;
	return rdata;
}

Data maxDelete(Heap * ph){
	Data rdata = ph->heapArr[1];
	Data lastData = ph->heapArr[ph->dataNum];
	int parentIdx = 1;
	int childIdx;
	
	while(childIdx = getHighPriChild(ph, parentIdx)){
		if(lastData.casherNo > (ph->heapArr[childIdx]).casherNo)
			break;
		
		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}
	
	ph->heapArr[parentIdx] = lastData;
	ph->dataNum -= 1;
	return rdata;
}

int main(){
	int N, k, a, b = 1;
	int time = 0;
	unsigned long long result = 0;
	Casher cArr[MAX_LEN];		//처음 입력받는 계산대 정보 저장
	
	Heap myheap;
	heapInit(&myheap);
	
	Heap maxheap;
	heapInit(&maxheap);
	
	scanf("%d %d", &N, &k);

	for(int i=0; i<N; i++){
		scanf("%d %d", &cArr[i].memNo, &cArr[i].prodNum);
	}
	
	do{
		//처음 입장 시작
		if(time==0)
		{
			//k개의 계산대(의 번호)가 손님에게 분배되며 완성된 계산대정보가 힙에 추가된다.
			for(a=0; a<k; a++){
				if(a>=N)
					break;
				cArr[a].casherNo = a;
				//printf("처음입장: %d님이 입장합니다.\n", cArr[a].memNo);
				heapInsert(&myheap, cArr[a]);
			}
		}
		
		//처음 입장이 아닌 경우, 시간은 흘러가고, 계산이 다 된 사람은 빠진다
		else
		{
			//printf("현재시각 : %d초\n", time);
			while(!isEmpty(&myheap)){
				if(myheap.heapArr[1].prodNum == time){
					//printf("%d님이 계산을 완료하였습니다.\n", myheap.heapArr[1].memNo);
					cArr[a].casherNo = myheap.heapArr[1].casherNo;
					cArr[a].prodNum += time;
					result += b * heapDelete(&myheap).memNo;
					b++;
					if(a < N){
						//printf("%d님이 입장합니다. 퇴장시간은 %d초입니다.\n", cArr[a].memNo, cArr[a].prodNum);
						heapInsert(&myheap, cArr[a++]);
					}
					else
						break;
				}
				
				else	//계산을 완료할 시간이 안 되었다면 반복문 종료
					break;
			}
			
			/*maxHeap에 임시 저장되어있던 사람들을 doneArr로 옮겨준다.
			while(!isEmpty(&maxheap)){
				doneArr[b] = maxDelete(&maxheap); 
				b++;
			}*/
		}
		time++;
		
	}while(!isEmpty(&myheap));
	
	printf("%lld\n", result);
}

b5460881 3년 전 0

단순 반복문을 사용하면 시간 복잡도가 O(N^2) 10만 *10만 이기 때문에 시간초과가 나므로 계산대 데이터를 저장하는 방식을 바꿔 시간복잡도를 줄일 새로운 알고리즘을 생각해 보는것이 좋겠네요

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

문제

문제

출처

ICPC

시간초과가 나는 이유가 뭘까요,,?

timosean 3년 전 0

b5460881 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말