글 읽기 - c++)시간을 더 줄일 수 있는 방법이 있을까요?(코드 주석 있음)

rootsquare 2년 전 0

영어로 된 사람의 이름을 목록에서 찾아 번호로 바꾸고, 이들을 union-find로 연결시킨 다음 집합의 크기를 계산해서 풀었으나 11%에서 시간 초과가 발생했습니다.

코드에 잘못된 풀이가 있거나, 더 효율적인 방법이 있는지 궁금합니다.

#include<stdio.h>
#include<string.h>
char people[200010][24];//사람 이름을 저장하는 배열. 행이 그 이름의 인덱스이다.
int connect[200010];//Union-find 용 배열
int answer[200010];//집합의 크기를 출력하는 배열. 처음에는 모두 다른 집합이므로, 모두 1로 초기화되어 있다.
void clear(void);
int isnew(int *num, char name[]);//사람 이름 찾기
int find_parent(int x);
int main(void)
{
    int test,line,num,p1,p2,tmp;
    int s1,s2;
    char ID1[24]={0},ID2[24]={0};
    scanf("%d",&test);//테스트 케이스의 수
    for(int k=1; k<=test; k++)
    {
        num=0;//현재까지 누적된 서로 다른 사람들의 수
        clear();//매 테스트 케이스마다 배열을 초기화한다.
        scanf("%d",&line);//친구 관계의 수
        for(int i=1; i<=line; i++)
        {
            scanf("%s %s",&ID1,&ID2);//두 사람의 이름을 입력한다.
            p1=isnew(&num,ID1);//두 사람의 인덱스 번호를 찾는다.
            p2=isnew(&num,ID2);
            if(p1>p2)
            {//p1<=p2하게 설정하였다. 이 경우 항상 s1<=s2이다.
                tmp=p1;
                p1=p2;
                p2=tmp;
            }
            s1=find_parent(p1);
            s2=find_parent(p2);
            if(s1!=s2)//두 사람이 서로 다른 네트워크(집합)에 있을 경우, 하나로 이어준다.
            {
                connect[s2]=s1;
                answer[s1]+=answer[s2];//s2 집합에 있는 모둔 원소가 s1로 들어간다.
            }
            printf("%d\n",answer[s1]);//s1집합의 크기가 해당 집합의 크기이다.
        }
    }
    return 0;
}
void clear(void)
{
    for(int i=1; i<=200000; i++)
    {//연결관계가 최대 10만 개이므로, 사람은 최대 20만 명.
        connect[i]=i;
        answer[i]=1;
        strcpy(people[i],"");
    }
}
int isnew(int *num, char name[])
{
    for(int i=1; i<=(*num); i++)
    {//현재까지의 목록에서 입력받은 사람 이름과 같은 이름이 있는지 확인한다.
        if(strcmp(people[i],name)==0)
        {//있으면 그 번호를 반환한다.
            return i;
        }
    }
    (*num)++;//없으면, 목록을 늘리고 목록의 마지막에 그 이름을 추가한다.
    strcpy(people[(*num)],name);
    return *num;
}
int find_parent(int x)
{//Union_find 함수
    if(x==connect[x])
    {
        return x;
    }
    else
    {
        return connect[x]=find_parent(connect[x]);
    }
}

willi19 2년 전 1

map 같은 자료구형을 이용해서 이름의 존재성을 좀 더 빨리 구하셔야 될 것 같습니다.

rootsquare 2년 전 0

map 사용해서 풀었습니다 감사합니다.

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

문제

문제

출처

ICPC

c++)시간을 더 줄일 수 있는 방법이 있을까요?(코드 주석 있음)

rootsquare 2년 전 0

willi19 2년 전 1

rootsquare 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말