Funcia
Lv.1countinghashsorting

많이 나온 순서로 정렬

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 nums를 다음 규칙으로 정렬한 배열을 반환하세요.

  1. 많이 나온 값이 앞에 옵니다.
  2. 나온 횟수가 같으면 값이 작은 쪽이 앞에 옵니다.

같은 값은 나온 횟수만큼 연달아 놓입니다.

입출력 예

numsresult
[4, 6, 2, 6, 4, 4, 6][4, 4, 4, 6, 6, 6, 2]
[1, 1, 2, 2, 2, 3][2, 2, 2, 1, 1, 3]
[5, -1, 3][-1, 3, 5]

입출력 예 설명

예 1 — 4와 6이 세 번씩 나오므로 작은 4가 먼저, 그다음 6, 한 번 나온 2가 마지막입니다.

예 2 — 2가 세 번, 1이 두 번, 3이 한 번 나옵니다.

예 3 — 모두 한 번씩 나오므로 값의 오름차순입니다.

효율성

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

함수 시그니처

solution(nums: int[]) → int[]

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

nums기대 출력
[4,6,2,6,4,4,6][4,4,4,6,6,6,2]
[1,1,2,2,2,3][2,2,2,1,1,3]
[5,-1,3][-1,3,5]

힌트

힌트

먼저 각 값이 몇 번 나오는지 해시 맵(또는 정렬 후 같은 값 묶기)으로 세어 두세요. 그다음 서로 다른 값들만 (횟수 내림차순, 값 오름차순) 기준으로 정렬하고, 각 값을 횟수만큼 이어 붙이면 됩니다.

복잡도 목표

원소마다 배열 전체를 훑어 횟수를 세면 O(N2)O(N^2)이 되어 효율성 테스트에서 시간 초과가 납니다. 횟수를 한 번에 세어 두면 정렬을 포함해 O(Nlog⁡N)O(N \log N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251696 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

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

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