문제링크: https://www.acmicpc.net/problem/1422

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

bool comp(const std::string& s1, const std::string& s2) {
	if (s1.length() == s2.length()) {
		return s1 > s2;
	}
	else {
		return s1.length() > s2.length();
	}
}

bool comp2(std::string s1, std::string s2) {
	return s1 + s2 > s2 + s1;
}

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

	int K;
	int N;
	std::cin >> K >> N;
	std::vector<std::string> v(K);
	std::vector<std::string> ans(N);
	int anssize = 0;

	for (int i = 0; i < K; i++) {
		std::cin >> v[i];
		ans[i] = v[i];
		anssize++;
	}

	std::sort(v.begin(), v.end(), comp);

	for (int i = anssize; i < N; i++) {
		ans[i] = v[0];
	}

	std::sort(ans.begin(), ans.end(), comp2);

	for (int i = 0; i < N; i++) {
		std::cout << ans[i];
	}
	std::cout << "\n";

	return 0;
}

난이도 치고는 문제를 굉장히 쉽게 풀었다.
벡터에 넣고 정렬한다. 길이가 긴 것 위주로, 길이가 같으면 수가 큰 것으로 넣는다.
ans벡터에는 모든 원소를 하나씩 다 넣고 N 크기에서 남은 공간에는 가장 큰 수를 채운다.
마지막으로 출력할 때 가장 큰 수가 되도록 정렬을 해주었는데..

이 comp2 sort에 큰 문제가 있었다...

노트

sort는 Strict weak ordering이라는 규칙이 지켜져야한다.
그 중 하나가 반대칭적(Antisymmetric)이라는 규칙이다.

처음에 함수를 만들 때,

bool comp2(std::string s1, std::string s2) {
	return s1 + s2 >= s2 + s1;
}

위처럼 작성해서 s1 + s2 == s2 + s1의 상황이 생기면 invalid comparator가 발생했다.

반대칭적 규칙 은 위 상황이 아닌 값은 무조건 반대값(true -> false, false -> true)이 나와야만 한다.
이는 복잡한 sort를 구현할 때 중요할 것이라고 생각되므로 반드시 숙지해야겠다.