문제
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요.
💡 입력설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다. 세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다. 각 배열의 원소는 int형 변수의 크기를 넘지 않습니다.
💡 출력설명
오름차순으로 정렬된 배열을 출력합니다.
💡 입력예제
3
1 3 5
5
2 3 6 7 9
💡 출력예제
1 2 3 3 5 6 7 9
코드
최종 풀이
#include <stdio.h>
#include <vector>
using namespace std;
int a[101], b[101], c[300];
int main () {
int n, m, i, p1 = 1, p2 = 1, p3 = 1;
scanf("%d", &n);
for(i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
for(i = 1; i <= m; i++) {
scanf("%d", &b[i]);
}
// p1, p2중 하나가 다 끝날 때까지 배열합치기
while(p1 <= n && p2 <= m) {
if(a[p1] < b[p2]) {
c[p3++] = a[p1++];
} else {
c[p3++] = b[p2++];
}
}
// p1이 남았을 경우
while(p1 <= n) {
c[p3++] = a[p1++];
}
// p2가 남았을 경우
while(p2 <= m) {
c[p3++] = b[p2++];
}
for(i = 1; i < p3; i++) {
printf("%d ", c[i]);
}
return 0;
}
설명
합칠 두 배열 a, b와 합쳐진 c배열을 전역변수로 선언(0으로 초기화하기 위해)하고 각 a와 b배열의 크기 n, m을 입력받아 해당 크기만큼 반복하여 수열을 각각 할당해놓는다.
두 배열의 크기가 다름으로
처음는 각 배열의 pointer가 하나라도 크기에 도달할때 까지 c에 할당한다.이후 a나 b중 pointer가 아직 도달하지 않았을 경우 남은 a 또는 b 배열의 값들을 c에 할당한다.마지막으로 c배열을 출력할 때 pointer가 증감연산자로 인해 1이 증가되어있으므로 pointer값의 미만까지 순회하여 값들을 출력한다.
배운 점
병합정렬
개념
요소를 쪼갠 후 다시 합병시키면서 정렬해나가는 방식이다.
시간복잡도
| 평균 | 최선 | 최악 |
| Θ(nlogn) | Ω(nlogn) | O(nlogn) |
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
