[백준 1422] 숫자의 신 (C#, C++) - soo:bak

문제 링크

1422번 - 숫자의 신

설명

K개의 자연수가 주어질 때, 모든 수를 한 번 이상 사용하고 총 N개의 수를 이어 붙여 만들 수 있는 가장 큰 수를 구하는 문제입니다.

접근법

먼저 K개의 수 중에서 가장 큰 수를 찾습니다. 길이가 가장 긴 수가 가장 크고, 길이가 같다면 사전순으로 큰 수를 선택합니다. 부족한 개수만큼 이 수를 추가하여 총 N개를 만듭니다.

이제 N개의 수를 이어 붙여 가장 큰 수를 만들어야 합니다. 두 수를 이어 붙이는 순서를 결정할 때, 두 가지 순서로 이어 붙인 결과를 비교하여 더 큰 결과가 나오는 순서를 선택합니다.

이 기준으로 정렬한 후 순서대로 이어서 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var first = Console.ReadLine()!.Split();
    var k = int.Parse(first[0]);
    var n = int.Parse(first[1]);

    var nums = new List<string>(k);
    for (var i = 0; i < k; i++) nums.Add(Console.ReadLine()!);

    var maxStr = nums[0];
    for (var i = 1; i < k; i++) {
      var s = nums[i];
      if (s.Length > maxStr.Length || (s.Length == maxStr.Length && string.Compare(s, maxStr, StringComparison.Ordinal) > 0))
        maxStr = s;
    }

    var all = new List<string>(n);
    all.AddRange(nums);
    for (var i = k; i < n; i++) all.Add(maxStr);

    all.Sort((a, b) => string.Compare(b + a, a + b, StringComparison.Ordinal));

    foreach (var s in all) Console.Write(s);
    Console.WriteLine();
  }
}

C++

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

typedef vector<string> vs;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int k, n; cin >> k >> n;
  vs v(k);
  for (int i = 0; i < k; i++) cin >> v[i];

  string maxStr = v[0];
  for (int i = 1; i < k; i++) {
    if (v[i].size() > maxStr.size() || (v[i].size() == maxStr.size() && v[i] > maxStr))
      maxStr = v[i];
  }

  vs all;
  all.reserve(n);
  for (int i = 0; i < k; i++) all.push_back(v[i]);
  for (int i = k; i < n; i++) all.push_back(maxStr);

  sort(all.begin(), all.end(), [](const string& a, const string& b) {
    return a + b > b + a;
  });

  for (auto &s : all) cout << s;
  cout << "\n";

  return 0;
}