글 읽기 - [C]시간초과 되는 이유 (4개 합이 0인 정수)

pmch0325 4년 전 0

안녕하세요

이진탐색으로 시간을 줄이고 lower bound와 upper bound로 중복 개수를 찾아주는게 이 문제의 포인트인것 같은데

개념은 대충 알지만 배운것이 없어서 그냥 무식하게 코드로 짰어요. 시간초과가 자꾸 뜨길래 혹시나 해서 중복 개수 찾을때도 이진탐색을 적용했구요.

아래 코드는 정답이라고 뜬 코드인데

아래 코드에서 배열을 선언할 때 입력을 받아 크기를 동적으로 할당했어요.

근데 원래는 동적으로 하지않고 문제에서 제시된 최대크기로 (배열A,B,C,D는 4000, 배열E,F는 4000^2인 16000000) 선언을 했는데 자꾸 시간초과가 되더라구요.

왜 선언해주는것 때문에 다른 에러도 아니고 시간초과가 되었던건지 모르겠습니다. 메모리를 할당해주는데도 시간이 많이 걸리나요?

애초에 문제에서 제시된 크기만큼 잡아준건데 이상이 생기면 안되는것 아닌가요? 아니면 코드가 뭔가 이상한건가요...

좀 지저분하게 짜서 코드에 빈틈이 있는건지 제가 이진탐색을 잘못 이해하고 있는건지 답은 맞았지만 개운하지가 않네요ㅠㅠ

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

int static compare(const void* f, const void* s) {
	if (*(int*)f > * (int*)s)
		return 1;
	else if (*(int*)f < *(int*)s)
		return -1;
	else
		return 0;
}

int main() {

	int a;
	long long result = 0;
	scanf("%d", &a);

	int* A, * B, * C, * D, * E, * F;
	A = (int*)malloc(sizeof(int) * a);
	B = (int*)malloc(sizeof(int) * a);
	C = (int*)malloc(sizeof(int) * a);
	D = (int*)malloc(sizeof(int) * a);
	E = (int*)malloc(sizeof(int) * a * a);
	F = (int*)malloc(sizeof(int) * a * a);
	for (int i = 0; i < a; i++)
		scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);

	for (int i = 0; i < a; i++) {
		for (int j = 0; j < a; j++) {
			E[a * i + j] = A[i] + B[j];
			F[a * i + j] = C[i] + D[j];
		}
	}

	int b;
	int c = a * a;
	int d;
	int x, y, x1;
	qsort(F, c, sizeof(int), compare);

	for (int i = 0; i < c; i++) {
		x = 0;
		y = c - 1;

		if (-E[i] >= F[0] && -E[i] <= F[y]) {
			while (x <= y) {                // 이진탐색
				a = y - x + 1;
				if (a % 2 == 0)
					b = a / 2 - 1;
				else
					b = a / 2;

				if (F[x + b] < -E[i])
					x = x + b + 1;
				else if (F[x + b] > -E[i])
					y = x + b - 1;
				else {
					d = x + b;                // 찾은 뒤 중복되는 원소 갯수 찾기
					x1 = x;
					result++;
					if (d + 1 < c) {
						if (F[d] == F[d + 1]) {
							x = d + 1;
							while (x < y) {
								a = y - x + 1;
								b = a / 2;

								if (F[x + b] == F[d])
									x = x + b;
								else
									y = x + b - 1;
							}
							result += (long long)x - d;
						}
                    }
                    if(d - 1 > 0) {
						if (F[d] == F[d - 1]) {
							x = x1;
							y = d - 1;
							while (x < y) {
								a = y - x + 1;
								if (a % 2 == 0)
									b = a / 2 - 1;
								else
									b = a / 2;

								if (F[x + b] == F[d])
									y = x + b;
								else
									x = x + b + 1;
							}
							result += (long long)d - x;
						}
					}
					break;
				}
			}
		}
	}

	printf("%lld", result);
	return 0;
}

sait2000 4년 전 1

틀린 코드를 올려주셔야 그 코드에 대한 답을 드릴 수 있습니다. 안 보고 알 순 없으니까요

sait2000 4년 전 1

다만 제 생각에는 1940ms이 나오는 코드가 살짝 어딘가가 빠른 거 아닐까 싶네요 컴파일러가 하는 최적화라던가 여러가지 요인이 많아서 그게 그거인 코드인데 2초를 살짝 넘어버린 거 아닐까요

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