7024 : 두 정렬 리스트 합병
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
이미 오름차순으로 정렬되어 있는 두 개의 리스트 $A$와 $B$가 주어집니다.
두 리스트의 모든 원소를 합치되, 여전히 오름차순 정렬된 상태를 유지하는 새로운 리스트를 만드는 프로그램을 작성하십시오.
[제약 조건]
• 두 리스트 크기 $N, M$: $1 \le N, M \le 50{,}000$
• 각 원소: $-10^9 \le a_i \le 10^9$ (오름차순 정렬)
두 리스트의 모든 원소를 합치되, 여전히 오름차순 정렬된 상태를 유지하는 새로운 리스트를 만드는 프로그램을 작성하십시오.
[제약 조건]
• 두 리스트 크기 $N, M$: $1 \le N, M \le 50{,}000$
• 각 원소: $-10^9 \le a_i \le 10^9$ (오름차순 정렬)
입력 설명
첫째 줄에 첫 번째 리스트의 크기 $N$과 두 번째 리스트의 크기 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 50000$)
둘째 줄에 오름차순으로 정렬된 $N$개의 정수가 공백으로 구분되어 주어집니다.
셋째 줄에 오름차순으로 정렬된 $M$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
둘째 줄에 오름차순으로 정렬된 $N$개의 정수가 공백으로 구분되어 주어집니다.
셋째 줄에 오름차순으로 정렬된 $M$개의 정수가 공백으로 구분되어 주어집니다. 각 정수의 범위는 $-10^9$ 이상 $10^9$ 이하입니다.
출력 설명
합병 및 정렬이 완료된 $N + M$개의 정수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 5
1 3 5
2 4 6 7 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4 5 6 7 8도움
이미 정렬된 두 배열을 합칠 때는 두 배열의 시작 위치를 가리키는 두 개의 포인터를 사용하는 두 포인터(Two Pointer) 알고리즘을 사용합니다. 각 단계에서 가리키는 값 중 작은 값을 새 배열에 넣고 포인터를 한 칸 전진시키면 $O(N + M)$의 시간에 효율적으로 정렬을 완료할 수 있습니다.