측량 기록 정리
문제
한 공사 현장의 지반이 얼마나 움직였는지 확인하기 위하여 두 측량팀이 현장에 들어갔다. 가 팀은 N개의 지점을, 나 팀은 M개의 지점을 각각 측정하였다.
각 측정값은 작년에 비하여 그 지점의 고도가 얼마나 바뀌었는지를 나타내는 정수다. 값이 양수면 그만큼 올라왔다는 뜻이고, 음수면 그만큼 내려앉았다는 뜻이다.
두 팀은 측정을 마친 뒤에 각자의 기록을 작은 값부터 큰 값 순서로 정리해 두었다. 현장 책임자는 두 팀의 기록을 한 줄로 합쳐서, 역시 작은 값부터 큰 값 순서로 늘어놓은 결과를 보려고 한다.
오름차순으로 정리된 두 팀의 기록이 주어졌을 때, 두 기록을 합쳐 오름차순으로 늘어놓은 결과를 출력하는 프로그램을 작성하여라.
예를 들어 N=2, M=2이고 두 팀의 기록이 다음의 표와 같다고 해보자.
| 팀 | 첫 번째 기록 | 두 번째 기록 |
|---|---|---|
| 가 팀 | 3 | 5 |
| 나 팀 | 2 | 9 |
두 기록은 각자 이미 오름차순으로 정리되어 있다. 그래서 전체를 처음부터 다시 정렬할 필요가 없다. 양쪽에서 아직 꺼내지 않은 값 가운데 맨 앞의 두 값만 견주어, 더 작은 쪽을 하나씩 꺼내 늘어놓으면 된다. 꺼내는 과정을 단계별로 정리하면 다음의 표와 같다.
| 단계 | 가 팀에서 볼 값 | 나 팀에서 볼 값 | 꺼낸 값 | 꺼낸 곳 |
|---|---|---|---|---|
| 1 | 3 | 2 | 2 | 나 팀 |
| 2 | 3 | 9 | 3 | 가 팀 |
| 3 | 5 | 9 | 5 | 가 팀 |
| 4 | 남은 값 없음 | 9 | 9 | 나 팀 |
한쪽 기록을 모두 꺼낸 뒤에는 다른 쪽에 남은 값을 순서대로 이어 붙이면 된다. 결과적으로 합친 기록은 2 3 5 9다.
양쪽의 맨 앞 값이 서로 같은 경우에는 어느 쪽에서 먼저 꺼내도 결과가 달라지지 않는다. 두 값이 같으므로 늘어놓은 모양도 같다.
한 팀의 기록 안에, 또는 두 팀의 기록 사이에 같은 값이 여러 번 나올 수도 있다. 이 경우에도 나온 횟수만큼 모두 늘어놓는다.
입출력 예시
예시 1
입력
2 2 3 5 2 9
출력
2 3 5 9
예시 2
입력
3 3 32251340 378089284 420241381 -341524412 302404239 826177827
출력
-341524412 32251340 302404239 378089284 420241381 826177827
예시 3
입력
2 1 -535832937 224336059 603724148
출력
-535832937 224336059 603724148
입력 조건
가장 먼저 첫째 줄에 가 팀이 측정한 지점의 수 N과 나 팀이 측정한 지점의 수 M이 공백으로 구분되어 주어진다. N과 M은 각각 1 이상 1,000,000 이하의 자연수다.
이어서 둘째 줄에 가 팀의 기록 N개가 공백으로 구분되어 한 줄에 주어진다.
이어서 셋째 줄에 나 팀의 기록 M개가 공백으로 구분되어 한 줄에 주어진다.
각 측정값은 절댓값이 1,000,000,000 이하인 정수다. 두 팀의 기록은 모두 오름차순으로 정리되어 주어지며, 같은 값이 여러 번 나올 수 있다.
입력 전체의 크기는 최대 약 8.8MB다. 한 줄에 수가 최대 100만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
두 기록을 합쳐 오름차순으로 늘어놓은 수 N+M개를 공백으로 구분하여 첫째 줄에 출력한다. 수와 수 사이에만 공백을 하나 넣으며, 줄의 마지막 수 뒤에는 공백을 붙이지 않는다. 출력할 수가 최대 200만 개이므로, 수를 하나씩 따로 출력하지 말고 하나의 문자열로 이어 붙여 한 번에 출력해야 한다.
요구사항
- 두 팀의 기록은 이미 각각 오름차순으로 정리되어 주어집니다
- 같은 값이 여러 번 나오면 나온 횟수만큼 모두 출력합니다
- 측정값은 음수일 수 있습니다
- 출력은 한 줄이며, 마지막 수 뒤에 공백이 남지 않습니다
- 합친 기록의 길이가 최대 200만이므로, 두 기록을 이어 붙인 뒤에 다시 정렬하는 방식은 시간과 메모리가 모두 빠듯합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 512MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
2 1 -535832937 224336059 603724148
-535832937 224336059 603724148
3 3 32251340 378089284 420241381 -341524412 302404239 826177827
-341524412 32251340 302404239 378089284 420241381 826177827
2 2 3 5 2 9
2 3 5 9
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.