C++ 백준 16496 (큰 수 만들기)

백준 16496 (큰 수 만들기)

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

16496번: 큰 수 만들기

---

간단한 정렬을 통해 풀 수있는 문제였다.

 

프로그래머스에도 똑같은 문제가 있는데, 프로그래머스에서 풀다가 백준에 똑같은 문제가 있길래 이 문제로 설명을 하겠다.

 

설명

---

아이디어는 간단하다.

어떤 문자열 A와 B가 있을 때 A+B가 큰지 B+A가 큰지를 비교해 정렬을 하면 된다.

 

아이디어는 참 간결하고 구현도 쉬운데 왜 티어가 플래티넘 5로 잡혀있는지 잘 모르겠다.

 

기존 프로그래머스에서 풀때는 일단 사전식으로 정렬을 한 뒤 530, 53054 와 같이 사전형으로도 비교가 안될 때만 A+B가 큰지 B+A가 큰지를 비교하면 된다고 해서 풀었는데, 생각해보니 모든 케이스에대해 해당 아이디어가 적용되므로 그냥 return (A+B > B+A)이런식으로만 해주면 된다.

 

에를 들어 245와 53이 있다면 24353 보다는 53245가 크기 때문에 큰숫자가 될때를 앞으로 보내주면 된다.

 

아 그리고 최종 답이 0일때, 그러니까 인풋이 0,0,0,0같이 들어오면 0000으로 출력될 수 가 있는데 이때만 0으로 나오게 처리를 해주면 된다.

 

구현

---

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

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

int main(void){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
	int a;
	cin>>n;
	vector <string> v;
	for(int i=0;i<n;i++){
		cin>>a;
		v.push_back(to_string(a));
	}
	sort(v.begin(),v.end(),compare);
	string ans="";
	if(v[0]=="0") {
		cout<<"0";
		return 0;
	}
	for(int i=0;i<v.size();i++){
		ans+=v[i];
	}
	cout<< ans;
	return 0;
}