백준 16496 큰 수 만들기

작성일 | In |

Problem : 큰 수 만들기

유형 : 그리디

문제 해석

  • 수를 나열하여 가장 큰 수가 되게 하여라
  • 숫자는 10억 이하이고 음수가 될 수 없다.
  • 수는 0으로 시작할 수 없다. (입력이 03 과 같이 들어오지 않는다.)
  • 000과 같은 형태의 결과인경우 0하나만 출력한다.

해결 전략

정렬기준을 새로 잡아준다.

  • 앞자리의 숫자가 큰 수들이 앞으로 와야한다. {9, 5 ....}
  • 맨 앞자리가 같은 숫자인 경우에 대한 정렬 처리가 필요하다.
    • 3, 30이 입력으로 들어왔을때, {3, 30} 이 되도록 해주어야한다.
    • 330이 303 보다 크기 때문이다.
  • 두 수를 이어 붙인뒤, 정렬해주면된다. 330 > 303

0 이 여러번 나오는 경우에 대해서는 예외처리를 해준다.

구현

정렬기준을 문자열기준 A + B > B + A로 해준다.

  • Cpp 기준 문자열 대소 비교는 330 > 303 을 잡아준다.
    • 굳이 숫자로 형변환을 해줄 필요가 없다.
  • 대신 30과 3을 비교할때는 3 < 30 으로 인식하므로, 이미 구현되어있는 소팅 알고리즘을 사용하지 못하여 다시 구현해준것이다.

정렬된 집합에서 맨앞의 숫자가 0이면, 뒤의 숫자들도 다 0이므로 0하나만 출력한다.
N이 1000밖에 안되므로 그냥 다른 숫자가 존재했는지 쭉 훑으며 확인해도 된다.

주의할 점

  • 0이 주어지는 경우 0 하나가 주어진다 라는 조건을 잘 보아야한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

void solve();

bool cmp(const string &num1, const string &num2);

bool isOnlyZero(const vector<string> &numbers);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("input.txt", "r", stdin);

  solve();

  return 0;
}

void solve() {
  int n;
  vector<string> numbers;

  cin >> n;
  while (n--) {
    string number;
    cin >> number;
    numbers.push_back(number);
  }

  sort(numbers.begin(), numbers.end(), cmp);

  if (isOnlyZero(numbers)) {
    cout << "0";
    return;
  }

  for (const string &number : numbers) {
    cout << number;
  }
}

bool cmp(const string &num1, const string &num2) {
  if (num1 == num2) return true;
  return num1 + num2 > num2 + num1;
}

bool isOnlyZero(const vector<string> &numbers) {
  return numbers[0] == "0";
}

// bool isOnlyZero(const vector <string> &numbers) {
//   for (const string &number : numbers) {
//     if (number != "0") return false;
//   }
//   return true;
// }

피드백

  • 모 회사 기술 면접에서 만났던 문제와 굉장히 유사하다.
  • 맨 앞 숫자만 0인지를 확인해서, 전체가 0인지를 확인하는 솔루션을 바로 생각해내지 못했었다.