Leetcode - 2231. Largest Number After Digit Swaps by Parity

문제

주어진 integer값를 다음의 조건에 부합하는 경우에 swap하여 가장 큰 수로 변환.

• 각 자리수는 짝수 끼리 혹은 홀수끼리만 swap할 수 있음.

https://leetcode.com/problems/largest-number-after-digit-swaps-by-parity/

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

해결

greedy 하게 해결. 가장 첫자리수를 가장 큰값으로 swap할수 있고 가장 앞자리가 가장 큰 수라는게 보장됨.

O(N^2)

void swap(char arr[], int a, int b)
{
    char temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
/* '0' ~ '9' -> 48 ~ 57 */
bool compare(char a, char b)
{
    int ap = a % 2;
    int bp = b % 2;
    if (ap != bp)
        return false;
    if (a > b)
        return true;
    else
        return false;    
}
void greedy(char arr[], int size)
{
    for (int st_idx = 0; st_idx < size - 1; st_idx++) {
        for (int i = st_idx + 1; i < size; i++) {
            if (compare(arr[i], arr[st_idx]))
                swap(arr, i, st_idx);
        }
    }
}
int largestInteger(int num){
    int ret = 0, size = 0;
    char arr[11] = {0,};
    
    sprintf(arr, "%d", num);
    size = strlen(arr);
    greedy(arr, size);
    sscanf(arr, "%d", &ret);
    return ret;
}