[백준 1377] 버블 소트 [C]

백준 - 1377

---

풀이

index를 이용해 쉽게 풀이할 수 있는 문제다.

bubble sort를 했을 때, 정렬이 다 되기까지의 횟수, 즉 요소들이 좌측으로 밀려났 횟수 중 가장 큰 횟수를 찾으면 된다.

 

입력받을 때 다음과 같이 index를 달아주고,

num	10	1	5	2	3
index	0	1	2	3	4

 

정렬을 하면 다음과 같은 모습이 된다.

num	1	2	3	5	10
index	1	3	4	2	0

 

정렬한 배열의 요소들에 달린 index값에 대해 이전의 index값들을 뺀 값들 중 최댓값이 정답과 일치한다.

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#define max(a, b) a > b ? a : b
typedef struct{
    int num, idx;
}Point;

int compare(const void *a, const void *b){
    return ((Point*)a)->num - ((Point*)b)->num;
}
int main(){
    int N;
    scanf("%d", &N);
    Point p[N];
    for (int i = 0; i < N; i++){
        scanf("%d", &p[i].num);
        p[i].idx = i;
    }
    qsort(p, N, sizeof(Point), compare);
	
    int result = 0;
    for (int i = 0; i < N; i++)
        result = max(result, p[i].idx - i);
    printf("%d", result+1);
}

---

출처

1377번: 버블 소트