WORDCHAIN 에서 런타임 에러가 발생하는 이유를 모르겠습니다

  • luku756
    luku756

    WORDCHAIN

    문제를 해결하였다고 생각하여 제출했는데 런타임 에러가 뜨더군요.
    RTE (SIGABRT: program aborted, probably assertion fail)
    RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)
    라는 에러가 발생하였습니다. 같은 코드를 여러번 제출하였는데 저 두가지 에러가 발생하더군요.

    코드는 다음과 같습니다.

    #include<stdio.h>
    #include<string.h>
    #include<string>
    #include<list>
    
    using namespace std;
    
    int start[30];
    int fin[30];
    char firstword,finishword;
    int size;
    
    list<string> str[30];
    
    void cal(int status){
        string now;
        int index;
        if(status == 1){
            for(int i=0;i<26;i++){
                if(start[i] > 0){
                    now = "";
                    now += str[i].front();
                    str[i].pop_front();
                    break;
                }
            }
        }
        else{
            now = str[firstword-'a'].front();
            str[firstword-'a'].pop_front();
        }
        size --;
        printf("%s ",now.c_str());
    
        while(size--){
            index = now[now.length()-1] - 'a';
    
            now = str[index].front();
            str[index].pop_front();
            printf("%s ",now.c_str());
        }
        printf("\n");
    
    }
    
    int possible(){
        int onfirst = 0, onfinish=0;
        for(int i=0;i<26;i++){
            if(start[i] != fin[i]){
                if(start[i] - fin[i] == 1){
                    if(onfirst == 1)
                        return -1;
                    onfirst=1;
                    firstword='a'+i;
                }
                else if(start[i] - fin[i] == -1){
                    if(onfinish == 1)
                        return -1;
                    onfinish=1;
                    finishword='a'+i;
                }
                else
                    return -1;
    
    
            }
        }
    
        if(onfirst == 1)
            return 0;
    
        return 1;
    
    }
    
    int main(){
        int TC,num,posi;
        string tmpstr;
        char tmp[130];
    
        scanf("%d",&TC);
    
    
        while(TC--){
            for(int i=0;i<30;i++){
                start[i]=0;
                fin[i]=0;
                str[i].clear();
            }
    
            scanf("%d",&num);
            size = num;
            while(num--){
                scanf("%s",tmp);
                str[tmp[0]-'a'].push_back(tmp);
                start[tmp[0]-'a']++;
                fin[tmp[strlen(tmp)-1]-'a']++;
            }
    
            posi = possible();
    
            if(posi == -1)
                printf("IMPOSSIBLE\n");
            else
                cal(posi);
                //printf("possible\n");
    
        }
    
    }
    

    재귀가 아니니 스택 오버플로우는 아니라 생각되어 나름대로의 워스트 케이스라고 생각되는 (한군데 데이터가 과도하게 집중된 경우) 50회, 100번의 aaaaaaaaaa 을 넣어봤는데 문제 없이 잘 작동하였습니다.

    무엇이 문제인지 알려주시면 감사하겠습니다 ㅠㅠ

    혹 list나 string의 일부 기능이 우분투 환경에서는 동작하지 않는다던가 하는 부분이 있나요? 코딩은 vs2010으로 진행하였습니다.


    10년 전
4개의 댓글이 있습니다.
  • Being
    Being

    startfin이 모두 같은 값일 때 startwordfinishword 값에 문제가 있을 것 같네요.


    10년 전 link
  • luku756
    luku756

    그 둘이 모두 같은 경우에는 cal에서 status를 1로 설정, 개중에 아무거나 찾아서 시작점으로 사용합니다. (firstword 등을 사용하지 않습니다) 실제로 전부 같은 예제를 실행시켜 보아도 에러가 발생하지 않습니다...


    10년 전 link
  • Kureyo
    Kureyo

    연결그래프가 아니어도 possible로 처리하는 경우가 있어서 해를 탐색하다가 str list가 소진되서 죽는 경우가 있을거 같네요~
    4
    ab
    ba
    cd
    dc
    로 해보세요


    10년 전 link
  • Kureyo
    Kureyo

    그리고 possible함수를 잡아도 cal돌면서 그래프가 분리되는 경우가 생길수있는데 이것도 방지해주셔야합니다
    5
    ax
    xy
    yx
    ab
    ba
    도 죽네요~


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.