글 읽기 - 1764번 듣보잡 런타임 에러

kuyoung05 5년 전 0

런타임 에러가 나네요 뭐가 문제나요?

#include 
#include 
int main() {
char listen[500000][21];
char see[500000][21];
int lsu;
int ssu;
int count = 0;
int i, j, k =0;
char ls[500][21];
scanf("%d %d", &lsu, &ssu);
for (i = 0; i < lsu; i++) {
scanf("%s", listen[i]);
}
for (i = 0; i < ssu; i++) {
scanf("%s", see[i]);
}
for (i = 0; i < ssu; i++) {
for (j = 0; j < lsu;j++) {
if (strcmp(see[i], listen[j]) == 0) {
count++;
strcpy(ls[k], see[i]);
k++;
}
}
}
printf("%d\n", count);
for (i = 0; i < k; i++) {
printf("%s\n", ls[i]);
}
}

yclock 5년 전 1

첫째로 Indentation이 전혀 되어있지 않습니다.

ls 배열의 크기를 확인해보세요.

kuyoung05 5년 전 0

ls배열의 크기를 바꿔도 안되요

yclock 5년 전 0

"시간 초과"와 "런타임 에러"는 다릅니다.

작성해주신 방법으로는 "시간 초과"를 피할 수 없습니다.

더 효율적인 알고리즘을 생각해보세요.

kuyoung05 5년 전 0

아 그렇군요 답변 감사드립니다.

kuyoung05 5년 전 0

그런데 배열크기에 따라 시간초과가 일어나기도 하고 안나기도 하는건 왜그런것인 가요?

yclock 5년 전 0

먼저, 배열의 크기가 충분히 클 경우 "시간 초과"가 나는 이유는, 본 알고리즘의 시간 복잡도가 O(NM)이기 때문입니다.

일반적으로 연산량이 1억 이내일 경우, 컴퓨터가 1초 안에 돌 수 있다고 생각합니다. 허나, 본 문제에서 NM = 2.5 * 10¹¹로 매우 큽니다. 따라서 본 소스 코드가 1초 안에 돌기를 기대하기는 어렵습니다.

배열의 크기가 위와 같이 "500" 정도로 작을 경우, 소스 코드 실행 이후 1초 이내에 "런타임 에러"가 발생하여 강제 종료될 수 있습니다. 이 경우 BOJ는 "시간 초과"가 아닌 "런타임 에러" 판정을 내립니다.

kuyoung05 5년 전 0

질문이 너무 많아 죄송합니다.. 시간복잡도에서 2.5 * 10¹¹ 이 식은 어떻게 나온건가요?

yclock 5년 전 0

18번째 줄부터 26번째 줄까지 코드의 시간 복잡도를 계산하면,

(i) 18번째 줄의 for문에 의하여 19번째 줄부터 25번째 줄까지 코드가 ssu번 실행되며

(ii) 19번째 줄의 for문에 의하여 20번째 줄부터 24번째 줄까지 코드가 lsu번 실행됩니다.

고로 본 소스 코드는 최소 ssu*lsu번 이상 연산을 한다고 생각할 수 있습니다.

lsu = N이고 ssu = M입니다. N과 M은 최대 500,000 이므로, N = M = 5 * 10⁵인 데이터에 대하여 적어도 (5 * 10⁵) * (5 * 10⁵) = 2.5 * 10¹¹번 연산을 합니다.

"알고리즘의 시간 복잡도"에 대하여 공부해보세요.

kuyoung05 5년 전 0

감사드립니다 알고리즘책 하나 사서 깊이 공부 해야 겠네요

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