C++[백준]16496번 큰 수 만들기

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

16496번: 큰 수 만들기

 

솔루션

---

플레티넘 치곤 아이디어를 떠 올리기가 그나마 쉬웠다. (다만 시간이 걱정되었는데,  통과가 됐다!)

 

처음에는 각 문자열마다 크기를 비교해서 더 큰 값이 나오는 즉시 바로 리턴을 하도록 operator를 작성 했다가.. 질문 게시판에 있는 반례에 걸렸다.

 

그 다음으로 생각을 한것이

 

각 문자열을 str +t.str, t.str + str 이렇게 두개를 더하여서 각 문자열끼리 비교하다가 어느 수가 더크다면 바로 리턴을 하도록 하였다.

 

만약 [0]번째 문자열의 첫 숫자가 '0' 이라면 바로 '0'만 출력하고 종료하도록 하였다.

 

 

코드

---

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

struct pa {
	int idx;
	string str;

	bool operator<(const struct pa& t)const {
		string tmp1 = str + t.str;
		string tmp2 = t.str + str;

		for (int i = 0; i < tmp1.size(); i++) {
			if (tmp1[i] == tmp2[i]) continue;
			return tmp1[i] > tmp2[i];
		}
		return idx > t.idx;
	}
};

struct pa arr[1002];
int N;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].str;
		arr[i].idx = i;
	}
	sort(arr, arr + N);
	
	if (arr[0].str[0] == '0') {
		cout << "0";
		return 0;
	}
	for (int i = 0; i < N; i++) {
		cout << arr[i].str;
	}
}