백준 10610번: 30

[문제 링크]

10610번: 30

---

30의 배수가 되기 위한 조건에는 2가지가 있다.

첫째, 반드시 0이 한개 이상 존재해야한다.

둘째, 각 자리수를 모두 더한 값이 3의 배수여야 한다.

 

위 조건을 검사하여 30의 배수가 가능한지 체크한 다음 불가능할 경우 -1 출력, 가능할 경우 N을 내림차순 정렬하여 그대로 출력해주면 원하는 결과를 얻을 수 있다.

 

처음엔 퀵정렬을 이용하여 정렬하였는데 정답은 받았지만 N의 최댓값이 100,000이기 때문에 효율성이 떨어졌다.

정렬할 숫자의 범위가 0~9로 제한되어 있다는 점을 이용하여 계수정렬로 정렬해 효율성을 높였다.

---

#include <iostream>
#include <string>
using namespace std;

void Quick_sort(string& data, int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] - '0' >= data[pivot] - '0')
			i++;
		while (j > start && data[j] - '0' <= data[pivot] - '0')
			j--;

		if (i > j)
		{
			char temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}
		else
		{
			char temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	
	Quick_sort(data, start, j - 1);
	Quick_sort(data, j + 1, end);

	return;
}

void Counting_sort(string& data)
{
	int arr[10] = { 0 };

	int len = data.length();
	for (int i = 0; i < len; i++)
		arr[data[i] - '0']++;

	int here = 0;
	for (int i = 9; i >= 0; i--)
		while (arr[i]--)
			data[here++] = i + '0';
}

int main(void)
{
	string N;
	cin >> N;

	int sum = 0, len = N.size();
	bool zeroCheck = false;
	for (int i = 0; i < len; i++)
	{
		if (N[i] == '0') zeroCheck = true;
		sum += N[i] - '0';
	}

	if (!zeroCheck || sum % 3 != 0)
		cout << -1 << endl;
	else
	{
		//Quick_sort(N, 0, len - 1);
		Counting_sort(N);
		cout << N << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 110 day