[ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬

해당 게시글에서는 여러 정수형 데이터로 우선순위가 나눠질 때,

효율적으로 처리할 수 있는 방법을 제시합니다.

 

몇몇 문제에서는 2가지 이상 기준에 의해 정렬되거나 우선순위가 정해집니다.

▶ [BOJ] 21608 상어 초등학교 (삼성 코딩 테스트 문제)

▶ [BOJ] 21609 상어 중학교 (삼성 코딩 테스트 문제)

 

만약, 사전순 배열과 같이 문자열 비교가 필요한 경우에는 아래 게시글 참고

▶ [ps] 문자열 사전 오름차순 비교 및 정렬  

[ps] 문자열 사전 오름차순 비교 및 정렬

 

구조체안에 등급과 누적 포인트를 의미하는 변수가 존재한다.

- 등급은 1~100까지 존재하면 높을수록 우선시 된다.

- 누적 포인트는 0점 ~ 10,000점 까지로 존재하면 높을수록 우선시 된다.

- 등급이 1차적으로 비교되며, 등급이 같은 경우 누적포인트로 2차 비교한다.

struct Data {
    int grade; // 등급
    int point; // 누적 포인트
}temp[N];

 

if문으로 기준 한개씩을 비교하는 경우에는 아래와 같이 구현할 수 있다.

#include <stdio.h>

const int N = 4;
struct Data {
    int grade; // 등급
    int point; // 누적 포인트
}temp[N];

Data arr[] = {
    { 10, 1000  }, { 99, 3000 }, { 10, 2000 }, { 80, 5000 },
};

bool comp(Data A, Data B) {
    if (A.grade > B.grade)
        return true;
    else if (A.grade == B.grade)
        return A.point > B.point;
    return false;
}

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end)
        return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end)
    {
        if (comp(arr[i], arr[j]))
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= end) temp[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i)
    {
        arr[i] = temp[i];
    }
}

int main() {
    printf("Before\n");
    for (int i = 0; i < N; ++i)
        printf("(%d, %d)\n", arr[i].grade, arr[i].point);

    mergeSort(0, N - 1);

    printf("\nAfter\n");
    for (int i = 0; i < N; ++i)
        printf("(%d, %d)\n", arr[i].grade, arr[i].point);
}

 

최적화

문제 조건을 잘 이용한다면 "등급"과 "누적 포인트"를 

하나의 수치로 표현해서 비교할 수 있다.

→ 등급이 최대 100 이고, 누적 포인트가 최대 10,000이기 때문에

    {등급 × 100,000 + 누적 포인트}로 계산하면 하나의 수치로 비교 가능하다.

    → 누적포인트가 등급 비교에 영향을 미치지 않도록 처리

#include <stdio.h>

const int N = 4;
const int MAX_GRADE = 1e2;
const int MAX_POINT = 1e4;
struct Data {
    int grade; // 등급
    int point; // 누적 포인트
    int prior; // 우선 순위 점수
    void setPrior()
    {
        prior = (grade * MAX_POINT * 10) + point;
    }
}temp[N];
Data arr[] = {
    { 10, 1000  }, { 99, 3000 }, { 10, 2000 }, { 80, 5000 },
};

bool comp(Data A, Data B) {
    return A.prior > B.prior;
}

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end)
        return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end)
    {
        if (comp(arr[i], arr[j]))
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= end) temp[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i)
    {
        arr[i] = temp[i];
    }
}

int main() {
    printf("Before\n");
    for (int i = 0; i < N; ++i)
    {
        arr[i].setPrior();
        printf("(%d, %d) => %d\n", arr[i].grade, arr[i].point, arr[i].prior);
    }

    mergeSort(0, N - 1);

    printf("\nAfter\n");
    for (int i = 0; i < N; ++i)
        printf("(%d, %d) => %d\n", arr[i].grade, arr[i].point, arr[i].prior);
}

- 데이터를 입력받을 때, 해당 수치를 Setting 해준다.

- 해당 수치로만 비교하여 정렬할 수 있다.

 

문제 조건에 따라서는 해당 수치가 int 범위를 벗어날 수 있다.

    int (4 Byte) → -2,147,483,648 ~ 2,147,483,647

    unsigned long (4 Byte) → 0 ~ 4,294,967,295

    ※ 32bit  (4Byte) 운영체제 기준 (운영체제에 따라 다름)

 

Reference

- [ps] 문자열 사전 오름차순 비교 및 정렬 

- [예제] 합병 정렬 (Merge Sort) 

- 시간 성능 향상을 위한 코드 최적화 (C/C++) 

- [ps] 순환되는 행렬 인덱스 (Index) 

- [BOJ] 21608 상어 초등학교 

- [BOJ] 21609 상어 중학교