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

문제를 풀다보면 ID가 작은 기준으로 하되,

동일한 ID인 경우에는 알파벳 오름차순으로 우선순위를 가지도록 하는 조건이 있습니다.

 

여러 기준에 의해 우선순위가 결정되는 경우 입니다.

숫자를 비교하는 경우에는 단순 비교를 하면 되지만, 아래 두가지를 처음 구현한다면 쉽지 않습니다.

 

대표적인 문제로 S사 코딩 기출 문제가 있습니다.

[BOJ] 백준 21608 상어 초등학교

[BOJ] 백준 21609 상어 중학교

 

구현

① 두 개의 기준 (ID, 이름) → comp() 함수 구현

② 알파벳 오름차순 기준 (문자열 비교) → strcmp() 이용

#include <stdio.h>

const int N = 4;
struct Data {
       int ID;
       char name[10];
}temp[N];

int strcmp(const char* s, const char* t) {
    while (*s && *s == *t) s++, t++;
    return *s - *t;
}

int comp(Data A, Data B) {
    if (A.ID < B.ID) return 1;
    else if (A.ID == B.ID)
        return strcmp(A.name, B.name) < 0;
    return 0;
}

void mergeSort(Data data[], int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    mergeSort(data, start, mid);
    mergeSort(data, mid + 1, end);
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (comp(data[i], data[j]))
            temp[k++] = data[i++];
        else
            temp[k++] = data[j++];
    }
    while (i <= mid) temp[k++] = data[i++];
    while (j <= end) temp[k++] = data[j++];
    for (i = start; i <= end; ++i) {
        data[i] = temp[i];
    }
}

int main() {
    Data data[] = { { 2, "ffff" }, { 3, "aaa" }, { 2, "ccccc" }, { 1, "zzzzzzz" }  };
       
    printf("Before\n");
    for (int i = 0; i < N; ++i) printf("(%d, %s)\n", data[i].ID, data[i].name);
    
    mergeSort(data, 0, N - 1);
    
    printf("\nAfter\n");
    for (int i = 0; i < N; ++i) printf("(%d, %s)\n", data[i].ID, data[i].name);
}

 

코드 설명

- 주어진 Data를 정렬하기 위해서 구조체와 Merge Sort를 이용했습니다.

- 어떤 Sort를 이용하든 상관없으면 Data를 비교할 때, comp() 함수로 처리합니다.

  

- strcmp()는 문자열에서 문자 하나씩 비교하는데, 아스키 코드값을 비교한다고 보시면 됩니다.

   ex) 'a' ~ 'z' ↔ 97 ~ 122 이며,  'A' ~ 'Z'  ↔ 65 ~ 90 입니다.

* 비교 기준에 따라 부등호 방향은 실제 결과를 보고 바꾸면 됩니다.