[Brute Force] 나3곱2

예제 입력 1

6

4 8 6 3 12 9

예제 출력 1

9 3 6 12 4 8

예제 입력 2

4

42 28 84 126

예제 출력 2

126 42 84 28

 

 

- 나3은 계속 숫자가 작아지고, 곱2는 숫자가 계속 커진다. 

- 각 수를 소인수분해하여,

조건1 - 3이 제일 많은 순

조건2 - 조건1이 같으면 숫자가 작은 순

위 조건으로 정렬하면 된다. 

 

#include <stdio.h>

using namespace std;
constexpr int MAX_SIZE = 100;

int N;

class number
{
public:
	long long num;
	long long cnt2;
	long long cnt3;

	number() {}

	number(int n) : num(n)
	{
		cnt2 = cnt3 = 0;
	}

	bool operator>=(number other)
	{
		if (cnt3 == other.cnt3) return num <= other.num;

		return cnt3 >= other.cnt3;
	}

	void updateCnt()
	{
		long long result = 0;
		long long tempNum = num;

		while (true)
		{
			if (tempNum % 3 == 0)
			{
				tempNum /= 3;
				cnt3++;
			}
			else break;
		}

		while (true)
		{
			if (tempNum % 2 == 0)
			{
				tempNum /= 2;
				cnt2++;
			}
			else break;
		}
	}
};
number nums[MAX_SIZE];
number tempNumber[MAX_SIZE];

void mergeSort(int start, int end)
{
	if (start >= end) return;

	int mid = (start + end) / 2;
	mergeSort(start, mid);
	mergeSort(mid + 1, end);
	
	int i = start;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= end)
	{
		if (nums[i] >= nums[j])
		{
			tempNumber[k++] = nums[i];
			i++;
		}
		else
		{
			tempNumber[k++] = nums[j];
			j++;
		}
	}

	while (i <= mid)
	{
		tempNumber[k++] = nums[i];
		i++;
	}
	while (j <= end)
	{
		tempNumber[k++] = nums[j];
		j++;
	}

	for (int i = start; i <= end; i++)
	{
		nums[i] = tempNumber[i - start];
	}
}

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

	for (int i = 0; i < N; i++)
	{
		long long input;
		scanf("%lld", &nums[i].num);

		nums[i].updateCnt();
	}

	mergeSort(0, N - 1);

	for (int i = 0; i < N; i++)
	{
		printf("%lld ", nums[i].num);
	}

	return 0;
}