Funcia
Lv.2arraygreedysortingstring

이어 붙여 만드는 가장 큰 수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
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"보다 큽니다.

효율성

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

함수 시그니처

solution(A: int[]) → string

제한 사항

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

기대 복잡도

시간
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.131130 ms도출됨
Java 251888 ms추정
Kotlin 2.4 (JVM)1888 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.