1422번 : 숫자의 신

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

1422번: 숫자의 신

K개 수 중 N개를 중복으로 뽑아서 가장 큰 수를 만드는 문제다. (단 모든 수를 다 써야 함)

아이디어 : 

숫자들을 잘 정렬하는 문제다. 우선 이 숫자들을 모두 문자열로 취급 할 것이다.
모든 문자열을 정렬해서, 순서대로 출력할 것이다.
출력할 때, 길이가 가장 긴 문자열은 N-K+1번만큼 연속으로 출력해준다.

구현 : 

문자열 x와 문자열 y의 우선순위를 비교할 때, x+y와 y+x를 비교한다. (여기서 +는 이어붙임을 의미함)
x+y가 y+x보다 사전순으로 더 크면, x가 먼저 와야하고, 그게 아니면 y가 먼저 와야 한다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
vector<pair<string, int> > v;
bool comp(pair<string, int> x, pair<string, int> y){
	int xl=x.first.size();
	int yl=y.first.size();
	string xtemp=x.first+y.first;
	string ytemp=y.first+x.first;
	for(int i=0; i<xl+yl; ++i){
		if(xtemp[i]!=ytemp[i]){
			return xtemp[i]>ytemp[i];
		}
	}
	return xl<yl;
}
int main(){
	int K,N; cin>>K>>N;
	int maxlen=-1;
	for(int i=0; i<K; ++i){
		string str; cin>>str; v.push_back({str,i});
		maxlen=max(maxlen, (int)str.size());
	}
	vector<pair<string,int> > temp;
	for(int i=0; i<v.size(); ++i){
		if(v[i].first.size()==maxlen){
			temp.push_back(v[i]);
		}
	}
	sort(v.begin(), v.end(), comp);
	sort(temp.begin(), temp.end(), comp);
	int flag=temp[0].second;
	for(int i=0; i<v.size(); ++i){
		if(v[i].second==flag){
			for(int j=0; j<N-K+1; ++j){
				cout << v[i].first;
			}
		}
		else{
			cout << v[i].first;
		}
	}
	cout << '\n';
}