C++ / 백준 / 1422 / 숫자의 신

문제

https://www.acmicpc.net/problem/1422

1422번: 숫자의 신

문제풀이

전에 백준에서 풀었던 16496번 문제와 거의 같은 문제이다.

16496번 문제와 다른 점은 입력에 0이 없다는 점과

입력받은 수보다 뽑아야 하는 수가 더 많을 수도 있다는 점이다.

1~9까지는 큰 수가 무조건 좋고, 9와 10 같은 경우도 자릿수가 늘어나므로 어느 수가 들어오든 큰 수를 여러 번 뽑는 것이 좋다.

 

먼저 숫자를 입력받는다, 만약 숫자가 더 필요하다면 입력받은 수 중 가장 큰 값을 계속 집어넣는다.

sort함수를 이용하여 정렬을 하고 추가로 조건을 만들어 a와 b를 이용해 a+b와 b+a 중 더 큰 값을 return 하도록 한다.

주의할 점은 int가 아닌 string으로 비교를 해야 한다.

a=10, b=9일 경우 int로 하면 9 < 10, string으로 하면 9 > 10 이기 때문이다.

이렇게 되면 결과가 달라지므로 string으로 비교해야 한다.

 

모든 정렬이 끝났으면 0부터  N까지 정렬된 값을 출력하면 된다.

 

코드

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


bool cmp(string a, string b) {
	return a + b > b + a;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int K(0), N(0), idx(0), big(0);

	cin >> K >> N;
	vector<string>num(N, "");

	for (idx = 0; idx < K; ++idx) {
		cin >> num[idx];
		big = max(big, stoi(num[idx]));
	}

	for (idx; idx < N; ++idx) {
		num[idx] = to_string(big);
	}
	sort(num.begin(), num.end(), cmp);

	for (idx = 0; idx < N; ++idx) {
		cout << num[idx];
	}
}