문제 출처

1. 문제설명

  • 숫자 N개가 주어질 때 그 수를 붙여서 만들 수 있는 가장 큰 수를 만들고자 한다.
  • 단, 모든 수는 적어도 한번 이용되어야 한다.



2. 알고리즘 설계

  • 숫자가 클수록 앞에 오면, 큰 값을 만들 수 있다.
  • 단, 주어진 숫자의 개수보다 자리수가 더 많을 수 있다.
    • 예제 2번을 보면 숫자는 2개인데 자리수는 4개를 만들어야 한다.



3. 로직

  • 문자열 정렬을 두 번 이용한다.
    • 숫자 하나씩 정렬을 하고,
    • N-K 개만큼, 하나의 값이 가장 큰 값으로 바꾼다.
    • 두 문자열을 붙였을 때 왼쪽에 붙인 것과 오른쪽에 붙인 걸 사전 순서대로 정렬한다.
      • 참고로, "10"과 "11" 중에 사전 순서는 후자가 뒤에 있다.
      • 그래서, 구현에 혼동이 오지 않음!



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

bool cmp(const string& a, const string& b) { return stoi(a) > stoi(b); }
bool cmp2(const string& a, const string& b) { return a + b > b + a; };

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

	int k, n;
	cin >> k >> n;
	
	vector<string> v(n);
	for (int i = 0; i < k; i++) cin >> v[i];
	sort(v.begin(), v.begin() + k, cmp);

	for (int i = k; i < n; i++) v[i] = v[0];
	sort(v.begin(), v.end(), cmp2);

	for (string s : v)
		cout << s;
	return 0;
}



5. 소감

  • 내가 처음으로 풀이한 solved.ac 기준 플레티넘 문제이다.
  • 중복처리 외에는 크게 까다롭지 않았다.
  • 아래와 같은 한가지 추측을 했었다.
    • 아스키 코드 값의 1~9까지는 순차적으로 되어있다.
    • string은 char의 배열이다.
    • 첫 번째 원소끼리 비교해서 같다면 두 번째 원소끼리 비교할 것이다.
  • pair 같은 경우도 first를 기준으로 정렬하지만,
    • first가 같으면 second를 기준으로 정렬하기 때문.
  • 내 추측은 들어맞았다!