백준 5836번 문제를 풀어서 제출했는데 segfault가 나왔습니다.
어느 정도 간 거 보니까 로직은 맞았는데... 무엇을 놓쳤을까 이런저런 확인을 하다가 큰 입력이 주어졌을 때 해당 콜을 뱉고 코드가 종료되었습니다.
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가 단순 리턴만 해도 같은 에러가 발생하는 것을 보니 벡터 크기의 문제
'프로그래밍 언어 정리 > C, C++' 카테고리의 다른 글
[C/C++] 포인터와 상수 (2) | 2023.04.23 |
---|---|
[C/C++] call by value, call by address(pointer), call by reference (0) | 2023.02.28 |
[C++] NULL과 nullptr (0) | 2023.02.19 |
[C++] 함수와 const (0) | 2022.12.08 |