글 읽기 - 시간 단축을 어떻게 해야 할 지 모르겠습니다.

kind4u 3년 전 0

단어 기준 정렬한 구조체로 구성된 배열과 등록 기준 정렬한 배열 두 종류의 배열을 생성 후,

번호 입력 시 인덱스에 맞는 출력값을 주고 단어 입력 시 이분탐색으로 해당 단어의 인덱스값을 찾아 출력하는 형식으로 짜봤습니다.

그런데 시간초과가 나는데 어디서 시간을 줄여야 할 지 감이 오지 않습니다.

반례나 시간을 줄일 방법이 있나요?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable:4996)

struct Array {
	char name[25];
	int num;
};

int compare(struct Array* num1, struct Array* num2) {
	return strcmp(num1->name, num2->name);
}

int binary_search(int str, int dst, char* input);
struct Array arr_name[100000];
char arr_num[100000][25];

int main() {
	int num, quiz;
	char input[25];
	int input_num;
	scanf("%d %d", &num, &quiz);
	for (int i = 0;i < num;i++) {
		scanf("%s", arr_name[i].name);
		strcpy(arr_num[i], arr_name[i].name);
		arr_name[i].num = i+1;
	}
	qsort(arr_name, num, sizeof(struct Array), compare);
	for (int i = 0;i < quiz;i++) {
		scanf("%s", input);
		if (input[0] >= '1' && input[0] <= '9') {
			input_num = atoi(input);
			printf("%s\n", arr_num[input_num-1]);
		}
		else
		{
			printf("%d\n", binary_search(0, num - 1, input));
		}
	}
	return 0;
}

int binary_search(int str, int dst, char* input) {
	char* target = arr_name[str + ((dst - str) / 2)].name;
	if (!strcmp(target, input)) {
		return arr_name[str + (dst - str) / 2].num;
	}
	else if (strcmp(target,input) == -1) {
		return binary_search(str + ((dst - str) / 2) + 1, dst, input);
	}
	else
	{
		return binary_search(str, str + ((dst - str) / 2) - 1, input);
	}
}

kind4u 3년 전 0

구현 당시 Array라는 map 형식 구조체를 구현했고, qsort로 정렬 후 name이라는 키 값을 기준으로 이분탐색을 이용하여 풀었다고 생각했는데 제가 잘못 이해하고 잘못 구현한 부분이 있나요?

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

문제

문제

출처

ICPC

시간 단축을 어떻게 해야 할 지 모르겠습니다.

kind4u 3년 전 0

kind4u 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말