글 읽기 - c++ sort compare 작성 질문

jiwoo2211 2년 전 0

입력받은 벡터 v1을 sort하려고 하는데 중복된 숫자를 받기 때문에 코드에 쓰여진 대로 compare 함수를 작성했는데 segFault가 떴습니다. 그래서 compare함수를 sort에 주지 않고 제출했는데 맞았더군요... compare함수에 잘못된 점이 있을까요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int i, int j)
{
    if (i <= j)
        return true;
    else
        return false;
}

int binSearch(vector<int> &t, int start, int end, int n)
{
    int ret = 0;
    int index = (start + end) / 2;
    if (t[index] < n)
    {
        ret = binSearch(t, index + 1, end, n);
    }
    else if (t[index] > n)
    {
        ret = binSearch(t, start, index - 1, n);
    }
    else
    {
        ret = index;
    }
    return ret;
}
int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    int N;
    cin >> N;
    // input
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < N; ++i)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
        v1.push_back(tmp);
    }
    sort(v1.begin(), v1.end(),compare);
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());

    for (int a : v)
    {
        int pos = lower_bound(v1.begin(), v1.end(), a) - v1.begin();
        cout << pos << " ";
    }
    return 0;
}

kipa00 2년 전 0

compare 함수는 operator< 조건(strict total order)을 만족해야 합니다. 즉

(irreflexive) 임의의 a에 대해 operator<(a, a)는 false여야 합니다.
(transitive) 임의의 a, b, c에 대해 operator<(a, b) && operator<(b, c)이면, operator<(a, c)는 true여야 합니다.
(connected) 임의의 a, b에 대해 operator<(a, b) && operator<(b, a)여서는 안 됩니다. (!operator<(a, b) && !operator<(b, a)이면 a와 b는 같은 것으로 간주됩니다.)

compare 함수를 operator<= 조건을 만족하도록 짜셨고, 이 경우 첫 번째와 세 번째 조건을 만족하지 않았기 때문에 어떤 일이 일어나도 이상하지 않습니다.

jiwoo2211 2년 전 0

아... 이거 전에 알고리즘 해결전략 책에서 얼핏 봤던것 같은데 제대로 공부안하니 여기서 통수를 맞네요... 역시 STL은 제대로 알고 써야 한다는 교훈을 줍니다.

감사합니다

그렇다면 원래 STL에 정의되어 있는 compare함수는 irreflexive를 만족해야 하기 때문에 두 값이 같은 경우는 구현되어있지 않나요?

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

문제

문제

출처

ICPC

c++ sort compare 작성 질문

jiwoo2211 2년 전 0

kipa00 2년 전 0

jiwoo2211 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말