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

16496번: 큰 수 만들기

 

문제

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

16496번: 큰 수 만들기

 

 

풀이

N개의 수를 이어붙여 가장 큰 수를 만들기 위해서 문자 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다.

 

출력 조건이 하나 더 있는데 만약 답이 0인 경우 "0" 하나만 출력해야 한다. 따라서 만약 0이 아닌 수가 한 번이라도 나왔다면 답이 0일 수 없으므로 N개의 수가 0 뿐인 경우에 0을 출력하고 그 외의 상황엔 위 기준에 따라 정렬한 수를 차례대로 출력하면 된다.

 

 

코드

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

bool cmp(string a, string b) {
  string ab = a + b;
  string ba = b + a;
  return ab > ba;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, flag = 0;
  cin >> n;
  vector<string> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if (v[i] != "0")
      flag = 1;
  }
  if (flag) {
    sort(v.begin(), v.end(), cmp);
    for (string i : v)
      cout << i;
  } else {
    cout << 0;
  }
  return 0;
}