Lv.2arraygreedysortingstring
이어 붙여 만드는 가장 큰 수
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
음이 아닌 정수 배열 A가 주어집니다.
원소들을 재배열해 이어 붙여 만들 수 있는 가장 큰 수를 문자열로 반환하세요.
모든 원소가 0이면 "0" 하나만 반환합니다("000"이 아닙니다).
입출력 예
| A | result |
|---|---|
[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
Expected complexity
- Time
- O(N log N * L)
- Space
- O(N * L)
Examples
| A | Expected |
|---|---|
[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
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 444 ms | estimated |
| C++ (GCC, gnu++23) | 444 ms | derived |
| Python 3.13 | 1130 ms | derived |
| Java 25 | 1888 ms | estimated |
| Kotlin 2.4 (JVM) | 1888 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |