글 읽기 - 52%쯤에서 자꾸 시간초과가 뜹니다ㅠㅠㅠ 도와주세요 알고리즘 초보입니다..

jhkang0516 1년 전 0

제가 각주에 -------------------------이렇게 시간 초과 줄이기 부분에서 시간이 조금 초과되는거 같은데... 줄이고 줄여도 저것보다 어떻게 줄여야 할지 감이 잘 안오네요ㅠㅠㅠ 힙정렬을 이용해서 정렬에서의 시간 복잡도는 줄인 것 같은데 binary search에서 시간 초과가 일어나는 거 같은데... 혹시 도움을 주실 수 있나요ㅠㅠ

답변 감사합니다!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define swap(type,x,y)do{type t=x;x=y;y=t;}while(0)

static void downheap(int a[], int left, int right)
{
	int temp = a[left];
	int child;
	int parent;
	for (parent = left; parent < (right + 1) / 2; parent = child)
	{
		int cl = parent * 2 + 1;
		int cr = cl + 1;
		child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
		if (temp >= a[child])
			break;
		a[parent] = a[child];
	}
	a[parent] = temp;
}

void heapsort(int a[], int n)
{
	int i;
	for (i = (n - 1) / 2; i >= 0; i--)
	{
		downheap(a, i, n - 1);
	}
	for (i = n - 1; i > 0; i--)
	{
		swap(int, a[0], a[i]);
		downheap(a, 0, i - 1);
	}
}
int bin_search(const int a[], int n, int key)//찾을 배열, 요소 개수, 검색할 값 
{
	int al = 0, ar = n - 1;//배열의 맨 왼쪽과 오른쪽
	int count = 1;	//key값이 나오는 횟수
	int ac;//배열의 가운데 인덱스
	do {
		//-----------------------------------시간 초과 줄이기
		ac = (al + ar) / 2;
		if (a[ac] == key)// 
		{
			while (a[ac - 1] == a[ac])//우선 중복값이 나오면 index를 최대한 왼쪽으로
				ac = ac - 1;
			
			while (a[ac + 1] == a[ac])//ac일 때와 ac+1일 때
			{
				ac = ac + 1;		//순서대로 하나씩 늘려가며 count++해주며 몇개가 중복되는지 찾아줌
				count++;
				if (a[ac] != a[ac + 1])//끝까지 갔으면 count반환
					return count;
			}
			return count;
		}
		//-----------------------------------------------
		else if (key > a[ac])
			al = ac + 1;
		else
			ar = ac - 1;
	}while(al <= ar);
	return -1;				//값이 검색 안되면 -1 반환
}
int main()
{
	int N, M;
	scanf("%d", &N);
	int* p;							//첫번째 입력되는 배열
	p = calloc(N, sizeof(int));
	for (int i = 0; i < N; i++)
		scanf("%d", &p[i]);
	scanf("%d", &M);
	int* q;							//두번째 입력되는 배열
	q = calloc(M, sizeof(int));
	for (int i = 0; i < M; i++)
		scanf("%d", &q[i]);

	int* a;							//배열a에 중복값을 넣어주기 위해 만듦
	a = calloc(M, sizeof(int));
	heapsort(p, N);
	
	for (int i = 0; i < M; i++)
	{
		if (bin_search(p, N, q[i]) != -1)		//검색값이 안되는 경우인 -1 제외
			a[i] = bin_search(p, N, q[i]);		//bin_search의 반환값은 중복값
	}
	for (int i = 0; i < M; i++)
		printf("%d ", a[i]);
	free(p);
	free(q);
	free(a);
}

djm03178 1년 전 0

https://www.acmicpc.net/board/... 와 같습니다.

jhkang0516 1년 전 0

감사합니다!

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

문제

문제

출처

ICPC

52%쯤에서 자꾸 시간초과가 뜹니다ㅠㅠㅠ 도와주세요 알고리즘 초보입니다..

jhkang0516 1년 전 0

djm03178 1년 전 0

jhkang0516 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말