Funcia
Lv.2arraygreedysortingstring

이어 붙여 만드는 가장 큰 수

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

음이 아닌 정수 배열 A가 주어집니다.

원소들을 재배열해 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환하세요.

모든 원소가 0이면 "0" 하나만 반환합니다("000"이 아닙니다).

입출력 예

Aresult
[3, 30, 34, 5, 9]"9534330"
[10, 2]"210"
[0, 0]"0"

입출력 예 설명

예 1 — 9, 5, 34, 3, 30 순서로 이어 붙입니다.

예 2 — "210"이 "102"보다 큽니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

Function signature

solution(A: int[]) → string

Constraints

  • 1≤N≤200,0001 \le N \le 200{,}000
  • 0≤A[i]≤1090 \le A[i] \le 10^9

Expected complexity

Time
O(N log N * L)
Space
O(N * L)

Examples

AExpected
[3,30,34,5,9]"9534330"
[10,2]"210"
[0,0]"0"

Hint

Hint

각 수를 문자열로 바꿔 사전순 내림차순으로 정렬하면 틀립니다. "3"과 "30"을 보면 사전순으로는 "30"이 크지만, 이어 붙이면 "330" > "303" 이라 "3"이 앞에 와야 합니다.

올바른 기준은 이어 붙여서 비교하는 것입니다. 두 문자열 a, b의 순서는 a+b와 b+a를 비교해 정합니다.

Array.Sort(strs, (a, b) => string.CompareOrdinal(b + a, a + b));

이 관계는 추이성을 만족하므로 전체를 이 기준으로 정렬하면 진짜 최댓값이 나옵니다.

두 가지 주의점입니다.

  • 문자열 비교는 문화권 비교가 아니라 Ordinal(문자 코드 순)로 하세요.
  • 결과의 첫 글자가 '0'이면 모든 원소가 0이라는 뜻이니 "0"을 반환하세요. 앞의 0을 전부 떼면 빈 문자열이 되어 틀립니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)444 msestimated
C++ (GCC, gnu++23)444 msderived
Python 3.131130 msderived
Java 251888 msestimated
Kotlin 2.4 (JVM)1888 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.