[백준 18870번] 좌표 압축 (C언어)

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

문제 설명

입력받은 수직선의 좌표를 압축하는 문제이다.

간단하게 압축 했을때의 결과값은 자신보다 작은 숫자의 개수가 몇개인지 세는 것이다.

 

예를 들어, 예제 입력 1에서

-10보다 작은 값은 0개이므로 좌표 압축의 결과는 0

4보다 작은 값은 -10, -9, 2 총 세개 이므로 좌표 압축의 결과는 3

 

코드 설명

* compare 함수는 qsort() 라이브러리를 사용하기 위해 만든 비교 함수이다.

* Coordinate 구조체는 숫자와 해당 숫자 좌표를 압축했을때 값을 저장하는 정수 변수로 이루어진다.

 

1. N입력 받은 후 N개의 구조체 배열을 동적할당 한다.

2. N개의 좌표를 입력받는다.

3. qsort()로 배열 오름차순 정렬

4. 반복문 안에서 해당 숫자보다 작은 숫자의 개수를 세는 작업으로 result 배열에 저장한다.

5. 압축된 좌표 출력

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Coordinate {
    int X, idx;
}coo;

int compare(const void* a, const void* b) {
    coo A = *(coo*)a;
    coo B = *(coo*)b;

    if (A.X > B.X)
        return 1;
    else if (A.X < B.X)
        return -1;
    else
        return 0;
}

int main() {
    int N;
    scanf("%d", &N);

    coo* arr = (coo*)malloc(sizeof(coo) * N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i].X);
        arr[i].idx = i;
    }

    qsort(arr, N, sizeof(coo), compare);

    int* result = (int*)malloc(sizeof(int) * N);
    int cnt = -1, min = -1000000000;
    for (int i = 0; i < N; i++) {
        if (arr[i].X != min) {
            min = arr[i].X;
            cnt++;
        }
        result[arr[i].idx] = cnt;
    }
    for (int i = 0; i < N; i++)
        printf("%d ", result[i]);
    return 0;
}

 

코드 작성시 사용한 C언어 개념

• 구조체
• 동적할당
• qsort() - 퀵정렬