Funcia
Lv.1arraytwo-pointers

정렬된 두 명단 합치기

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

두 반의 학생 점수가 각각 오름차순으로 정렬된 배열 a와 b로 주어집니다. 두 반을 합친 전체 점수 명단을 오름차순으로 정렬된 하나의 배열로 반환하세요. 같은 점수는 모두 남깁니다.

입출력 예

abresult
[1, 4, 7][2, 3, 8, 9][1, 2, 3, 4, 7, 8, 9]
[][5, 5][5, 5]
[-3, 0, 0][0, 10][-3, 0, 0, 0, 10]

입출력 예 설명

예 1 — 두 명단의 맨 앞을 비교해 더 작은 쪽을 차례로 꺼내면 됩니다.

예 2 — 한쪽 반이 비어 있을 수도 있습니다.

예 3 — 두 명단에 같은 점수가 있으면 모두 결과에 들어갑니다.

효율성

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

함수 시그니처

solution(a: int[], b: int[]) → int[]

제한 사항

  • 0≤0 \le a.length, b.length ≤100,000\le 100{,}000, 1≤1 \le a.length + b.length
  • −109≤-10^9 \le a[i], b[i] ≤109\le 10^9
  • a와 b는 각각 오름차순(같은 값 허용)으로 정렬되어 있습니다.

기대 복잡도

시간
O(N + M)
공간
O(N + M)

입출력 예

ab기대 출력
[1,4,7][2,3,8,9][1,2,3,4,7,8,9]
[][5,5][5,5]
[-3,0,0][0,10][-3,0,0,0,10]

힌트

힌트

두 배열에 각각 포인터 i, j를 두고, a[i]와 b[j] 중 작은 쪽을 결과에 넣은 뒤 그 포인터만 한 칸 옮깁니다. 한쪽이 끝나면 다른 쪽의 남은 원소를 그대로 붙입니다.

복잡도 목표

b의 원소를 하나씩 a의 알맞은 자리에 끼워 넣으면 끼울 때마다 뒤의 원소를 밀어야 해서 O(N×M)O(N \times M)으로 시간 초과입니다. 두 포인터로 한 번에 합치면 O(N+M)O(N + M)입니다.

언어별 시간 제한

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

테스트 그룹

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

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