글 읽기 - 구조체로 구현할 때의 문제

maosadao 4년 전 0

정렬하기 전과 후의 인덱스를 비교하여 그 차이의 최댓값에 +1을 하는 방식으로 풀었습니다. 그런데 아래소스코드 그대로 제출했을 때는 ac를 받지 못했는데compare() 부분을

bool compare(A x, A y)

{

if(x.size!=y.size) return x.size < y.size;

return x.num < y.num;

}

이렇게 수정했더니 ac가 뜨더군요. 혹시 값(size)이 같을때 인덱스(num)의 비교가 왜 필요한지 그 예시랑 같이 알려 주실수 있나요? 저는 size가 같으면 정렬전, 중, 후에도 num은 배열 상에서 뒤에 있는게 앞에있는거 보다 당연히 크다고 생각해서 잘 모르겠네요ㅠㅠ

#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
struct A {
    int num;
    int size;
} a[500001];
int comp[500001];
int n,m;

bool compare(A x, A y)
{
    return x.size < y.size;
}

void input(void)
{
    scanf("%d",&n);

    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i].size);
        a[i].num=i;
    }
}

void process(void)
{
    sort(a+1,a+n+1,compare);

    for(int i=1; i<=n; i++)
    {
        comp[i]=a[i].num-i;
        m=max(m,comp[i]);
    }
}

void output(void)
{
    printf("%d",m+1);
}

int main()
{
    input();
    process();
    output();
    return 0;
}

Stable sort와 unstable sort의 차이입니다. 가중치가 같은 여러 원소들끼리의 상대적 순서가 정렬후에도 보존되는것을 stable하다고 하는데, 버블소트는 stable하지만 std::sort는 stable하다고 보장되지 않으며(보통의 구현체에서는 unstable합니다), 그래서 std::sort에서 stable한 정렬을 원한다면 원래의 인덱스 또한 비교의 가중치로 주어야 합니다. 혹은 std::stable_sort라는 선택지도 있습니다.

maosadao 4년 전 0

헉 단번에 이해되는 깔끔한 설명 감사합니다!

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

문제

문제

출처

ICPC

구조체로 구현할 때의 문제

maosadao 4년 전 0

domece 4년 전 3

maosadao 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말