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;
}
Author And Source
이 문제에 관하여(Leetcode - 2231. Largest Number After Digit Swaps by Parity), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soopsaram/2231.-Largest-Number-After-Digit-Swaps-by-Parity저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)