본문 바로가기

프로그래밍 언어 정리/C, C++

[C/C++] bad_array_new_length

백준 5836번 문제를 풀어서 제출했는데 segfault가 나왔습니다.

 

어느 정도 간 거 보니까 로직은 맞았는데... 무엇을 놓쳤을까 이런저런 확인을 하다가 큰 입력이 주어졌을 때 해당 콜을 뱉고 코드가 종료되었습니다.

 

모를 땐 chat gpt

 

chat gpt말고도 더 검색해보니... sort를 할 때 벡터가 매우 크거나, 사이즈로 음수를 참조하는 일이 발생하면 위와 같은 에러를 발생시킨다고 합니다. 벡터가 동적이다 보니 이런 일이 발생합니다.

 

문제는 벡터의 크기는 900미만에 내부벡터의 크기도 약 10내외정도로 큰 크기는 아니었습니다.

또 cmp를 빼주니 멀쩡히 돌아갑니다.

벡터의 크기가 크지 않았음을 이용하여 직접 선택정렬을 구현하는 방식으로 문제를 해결하였습니다.

 

추론을 해보자면 다차원 벡터이면서, 직접 정렬방법을 구현하고, 절대적으로 큰 크기는 아니지만 어느 정도 벡터의 크기가 있다면, 해당 에러가 발생하는 듯 합니다.

해당 에러를 발생시키기 위해 1000 * 1000벡터를 cmp로 정렬시켜봤는데도 다시는 저 에러를 볼 수 없었습니다.

아직도 왜 발생했는지는 모르겠습니다.

 

만약 이 에러가 발생한다면 시간은 조금 걸리겠지만 직접 배열을 정렬하는 식으로 해결이 가능합니다.

저는 인풋이 작아서 선택정렬로 해결했습니다.

 


문제의 코드 일부분

 

    int n = 0;
    ifs >> N >> C;
    map<Point, int> temp;

    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2; ifs >> x1 >> y1 >> x2 >> y2;
        Point p1 = Point(x1, y1), p2 = Point(x2, y2);

        if (temp.insert(make_pair(p1, n)).second) {
            ++n;
        } if (temp.insert(make_pair(p2, n)).second) {
            ++n;
        }

        int pp1 = temp[p1], pp2 = temp[p2];
        points[pp1] = p1; points[pp2] = p2;
        adj[pp1].push_back(pp2);
        adj[pp2].push_back(pp1);
    }

    int size = 0;
    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;

        fences.push_back(vector<Point>());
        dfs(i, size++);
    }

    sort(fences.begin(), fences.end(), cmp);
    // cmp가 단순 리턴만 해도 같은 에러가 발생하는 것을 보니 벡터 크기의 문제