CodeUp[Q_2704] : 30진수 정렬

1. 문제

https://codeup.kr/problem.php?id=2704

30진수 정렬

[출처 : 코드업(https://codeup.kr/)]

이번에는 여러개의 30진수가 입력되면 내림차순으로 정렬하는 문제입니다.

30진수 자체로 정렬하면 매우 복잡하기 때문에

10진수로 변환하고 이를 정렬하는 방법으로 해결하시면 됩니다.

 

30진수를 10진수로 변환하는 방법을 16진수-2진수 변환과 비슷하기 때문에 이전 글을 참고해 주세요.

2020/03/20 - [프로그래밍/CodeUp] - CodeUp[Q_2026] : 16진수를 2진수로 변환하기

그리고 저는 정렬 알고리즘 중 퀵 정렬 알고리즘을 사용했습니다.

 

 

2. 풀이방법

STEP 1. 30진수를 10진수로 변환하는 함수 작성

STEP 2. 정렬 알고리즘 작성

 

 

3. 해답

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

int arr1[15000];
char arr2[15000][7];

int toi(char* s) {
	// 30진수를 10진수로 변환
	int tmp = 0;
	int sum = 0;
	for (int i = 0; i < strlen(s); i++) {
		tmp = (int)s[i];
		if ((tmp >= 48) && (tmp <= 57)) tmp -= 48;
		else if ((tmp >= 65) && (tmp <= 90)) tmp -= 55;

		sum = (sum * 30) + tmp;
	}
	return sum;
}

void SWAP1(int* a, int* b) {
	// 정수 스왑
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void SWAP2(char *a, char *b) {
	// 문자열 스왑
	char tmp[7];
	strcpy(tmp, a);
	strcpy(a, b);
	strcpy(b, tmp);
}

void my_qsort(int left, int right) {
	// quick sort 알고리즘
	int pl = left;
	int pr = right;
	int x = arr1[(pl + pr) / 2];

	do {
		// 내림차순으로 정렬
		while (arr1[pl] > x) pl++;
		while (arr1[pr] < x) pr--;
		if (pl <= pr) {
			SWAP1(&arr1[pl], &arr1[pr]);
			SWAP2(arr2[pl], arr2[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);
	if (left < pr) my_qsort(left, pr);
	if (pl < right) my_qsort(pl, right);
}

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

	for (int i = 0; i < n; i++) {
		scanf("%s", arr2[i]);
		arr1[i] = toi(arr2[i]);
	}

	my_qsort(0, n - 1);

	for (int i = 0; i < n; i++) {
		printf("%s ", arr2[i]);
	}

	return 0;
}