백준 1427 소트인사이드 C/C++

소트인사이드 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

62973

40368

33869

64.467%

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

 

예제 입력 1 복사

2143

예제 출력 1 복사

4321

예제 입력 2 복사

999998999

예제 출력 2 복사

999999998

예제 입력 3 복사

61423

예제 출력 3 복사

64321

예제 입력 4 복사

500613009

예제 출력 4 복사

965310000

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

using namespace std;



void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}



int arr[100001];
int main(void)
{
	int n,tmp,cnt=0,i=0;
	
	cin >> n;
	tmp = n;
	while (n > 0)
	{
		
		tmp=n %10;
		arr[i]=tmp;
		cnt++;
		i++;
		n =n/ 10;
	}
	MergeSort(arr, 0, cnt - 1);
	for (int i=cnt-1; i >= 0; i--)
	{
		printf("%d", arr[i]);
	}

	


	return 0;
}

 

값을 받아서 정렬하는 것이다.

병합정렬(윤성우의 열혈 자료구조 책에서 코드 사용)

 

값을 받아서 배열에 넣어서 정렬했다.

2143/10을 하면 214가 된다

2143%10을 하면 3이 된다

 

이 과정을 통해 하나씩 배열에 값을 넣는다.

이후에 값을 역순으로 출력한다.