Lv.2arraygreedysortingstring
이어 붙여 만드는 가장 큰 수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 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"보다 큽니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(A: int[]) → string
제한 사항
기대 복잡도
- 시간
- O(N log N * L)
- 공간
- O(N * L)
입출력 예
| A | 기대 출력 |
|---|---|
[3,30,34,5,9] | "9534330" |
[10,2] | "210" |
[0,0] | "0" |
힌트
힌트
각 수를 문자열로 바꿔 사전순 내림차순으로 정렬하면 틀립니다. "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을 전부 떼면 빈 문자열이 되어 틀립니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 444 ms | 추정 |
| C++ (GCC, gnu++23) | 444 ms | 도출됨 |
| Python 3.13 | 1130 ms | 도출됨 |
| Java 25 | 1888 ms | 추정 |
| Kotlin 2.4 (JVM) | 1888 ms | 추정 |
| C# 14 (.NET 10) | 1000 ms | 도출됨 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |