Lv.1arraytwo-pointers
정렬된 두 명단 합치기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
두 반의 학생 점수가 각각 오름차순으로 정렬된 배열 a와 b로 주어집니다. 두 반을 합친 전체 점수 명단을 오름차순으로 정렬된 하나의 배열로 반환하세요. 같은 점수는 모두 남깁니다.
입출력 예
| a | b | result |
|---|---|---|
[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[]
제한 사항
-
a.length,b.length,a.length + b.length -
a[i],b[i] a와b는 각각 오름차순(같은 값 허용)으로 정렬되어 있습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| a | b | 기대 출력 |
|---|---|---|
[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의 알맞은 자리에 끼워 넣으면 끼울 때마다 뒤의 원소를 밀어야 해서 으로 시간 초과입니다. 두 포인터로 한 번에 합치면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1592 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |