16496 큰 수 만들기

백준 16496 ←클릭

변수 설정

nums[i] : 입력된 수의 각 자리 숫자 저장
cnt : 입력된 수가 몇자리 수인지
pq: 정렬을 위한 우선순위 큐

아이디어

• 입력 숫자에 대해서 10자리까지 계속 반복하는 새로운 수를 만든다.
  
  
• 예를 들어 100이면 100 100 100 1으로 반복하여 1001001001, 2050이면 2050 2050 20으로 반복하여 2050205020
  
  
• 연속해서 만든 수를 기준으로 내림차순으로 정렬한다.

예시

입력으로 100 1004 10가 들어왔다고 하자

100은 1001001001, 1004는 1004100410, 10은 1010101010. 이들을 정렬하면
1010101010 > 1004100410 > 1001001001 이므로
10 1004 100 즉 101004100가 정답이 된다.

증명

연속 숫자는 입력 숫자 뒤에 올 수 있는 최대한 큰 값이라고 생각하면 된다.
위 예시를 들면 일단 맨 앞에 10이 오는 것은 모두 생각할 수 있다.
이제 100 과 1004중 어떤 수가 먼저 오는지 결정해야 한다.
만약 100이 1004를 이기기 위해서 100뒤에 4▢▢▢▢ 가 와야한다. 하지만 100뒤에 4▢▢▢▢는 절대 못온다. 왜냐하면 만약 4▢▢▢▢가 있다면 이미 100앞에 있을 것이기 때문이다. 그러면 100뒤에 올 첫번째 숫자는 무엇일까? 무조건 1이다. 사실 1보다 작거나 같은 수 인데 0은 올 수 없기에 1밖에 안되는 것이다.
헷갈리니 100과 1004 대신 200과 2004를 예시로 들면, 200뒤에 올 숫자는 2또는 1이다. 3또는 3보다 큰 수가 있다면 이미 200앞에 있을 것이기 때문이다. 운 좋게 2가 왔다고 하자. 그러면 2002뒤에 올 수는 무엇일까? 2002 뒤에는 0밖에 못온다. 만약 1또는 1보다 큰 수가 있다면 200앞에 왔을 것이기 때문이다. 이런식으로 반복하면 200이 올 경우 가장 운이 좋은 경우에 될 수 있는 수: 200 200 200 2이고 이 수를 기준으로 순위를 매길 수 있다. 이 수를 기준으로 내림차순 정리를 하는 것이다.

시간복잡도

우선순위 큐를 사용한 정렬이므로 $O(nlogn)$

코드

#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#include<iostream>
#include<queue>
#include<cmath>
#include<string>
using namespace std;
struct cmp {
	bool operator()(pair<ll, int>& a, pair<ll, int>& b) {
		return a.first < b.first; //첫번째 인자 기준 내림차순
	}
};
pair<ll, int> make_number(int input);
bool print = false;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, cmp> pq;
int N;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int input;
		cin >> input;
		pq.push(make_number(input));
	}
	bool only_zero = true; //0밖에 없는 경우 예외 처리
	string ans;
	while (!pq.empty()) {
		if (pq.top().second != 0) only_zero = false;
		ans.append(to_string(pq.top().second));
		pq.pop();
	}
	if (only_zero) cout << "0" << endl;
	else cout << ans << endl;
	
	return 0;
}

pair<ll,int> make_number(int input) {
	int cnt = 0;
	int save_input = input;
	int nums[10] = { 0, };
	if (input < 10) {
		cnt = 1;
		nums[0] = input;
	}
	else {
		while (input != 0) {
			nums[cnt] = input % 10;
			cnt++;
			input /= 10;
		}
	}
	ll return_val = 0;
	for (int i = 0; i <= 9; i++) { //연속 수를 만드는 코드
		return_val += nums[(cnt-1)-(i%cnt)] * (pow(10, 9 - i));
	}
	
	return make_pair(return_val,save_input);
}

느낀 점

사실 내가 푼 방식이 통과는 하지만 수학적으로 맞는 풀이 인지는 모르겠다... 이 문제를 풀고 다른 사람의 풀이를 참고하였는데 두 숫자 A, B를 문자열로 변환해서 A+B, B+A로 만들고 그 수를 기준으로 정렬을 한다고 하는데 그 방법이 직관적으로 맞는거 같지만 증명 방법에 대해서는 잘 모르겠다.