글 읽기 - 시간 초과 질문드립니다.

yeongmo 5년 전 0

구조체 배열을 이용해 이름을 하나씩 저장하는 방법을 썼습니다.

strcmp와 strcpy함수로 이용하는 방법을 사용했는데

시간 초과가 납니다...ㅠㅠ 어떻게 해야 시간초과를 줄일 수 있을까요?

처음에는 string.h 안쓰고 문자열에서 문자 하나하나 비교해가는 방법으로 사용했으나

시간초과가 떠 바꾼 방법인데도 그러니 너무 막막합니다 ㅜ

도움 부탁드립니다

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

typedef struct
{
    char name[21];
} Person;

int main (void)
{
    int N,M;
    Person *duddo;
    Person *bodo;
    Person *res;
    int i,j;
    int count=0;
    
    scanf("%d %d",&N, &M);
    
    duddo=calloc(N, sizeof(Person));
    bodo=calloc(M, sizeof(Person));
    res=calloc(N, sizeof(Person));
    
    for (i=0 ; i<N ; i++)
    {
        scanf("%s",duddo[i].name);
    }
    for (i=0 ; i<M ; i++)
    {
        scanf("%s",bodo[i].name);
    }
    
    for (i=0 ; i<N ; i++)
    {
        for (j=0 ; j<M ; j++)
        {
            if (strcmp(duddo[i].name, bodo[j].name)==0)
            {
                strcpy(res[count].name, duddo[i].name);
                count++;
            }
        }
    }
    
    printf("%d\n",count);
    
    for (i=count-1 ; i>=0 ; i--)
    {
        printf("%s\n",res[i].name);
    }
    
    return 0;
}

kimsy96 5년 전 0

O(NM)풀이는 시간제한을 피할길이 없어보입니다

N M제한이 커서..

자료의 저장과 탐색이 빠른 자료구조를 사용해서 풀거나 (이 경우 STL을 사용하면 간단하게 풀 수 있습니다)

그게 아니라면 이분탐색을 이용한 풀이가 있겠네요

chogahui05 5년 전 0

O(len x n) 혹은 O(len x m) 정도에 푸시려면 트라이 이용해 보세요.

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

문제

문제

출처

ICPC

시간 초과 질문드립니다.

yeongmo 5년 전 0

kimsy96 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말