[백준/11728/C언어] 배열 합치기 _ 풀이

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

---

풀이

선택정렬(내림차순)을 활용한 필자의 초기 풀이 (답x)

	#include <stdio.h>
	int a[1000000], b[1000000];
	int ab[1000000]; 
	int main() {
		int an, bn;
	
		int temp;
		scanf("%d %d", &an, &bn);

		for (int i = 0; i < an; i++)
			scanf("%d", &a[i]);
		for (int i = 0; i < bn; i++)
			scanf("%d", &b[i]);

		for (int i = 0; i < an; i++) {
			ab[i] = a[i];
		}
		for (int i = an; i < an + bn; i++) {
			ab[i] = b[i-an];
		}

		for (int i = 0; i < an + bn; i++) {
			for (int j = i+1; j < an + bn; j++) {
				if (ab[i] > ab[j]) {
					temp = ab[j];
					ab[j] = ab[i];
					ab[i] = temp;
				}
			}
		}
	
		for (int i = 0; i < an + bn; i++) printf("%d ", ab[i]);

		return 0;
	}

필자는 처음에 배열 두개를 합해 새로운 배열을 만들어 내림차순으로 정렬했다.

에디터상 문제없는 풀이과정이다.

다만 시간제한으로 인해 정답은 되지 못한다.

 

병합정렬(merge sort) 알고리즘 풀이

	#include <stdio.h>
	int a[1000000], b[1000000];		// 오버플로우 방지를 위해 전역변수 설정

	int main() {
		int an, bn;
		int p = 0, q = 0;
		scanf("%d %d", &an, &bn);

		for (int i = 0; i < an; i++)
			scanf("%d", &a[i]);
		for (int i = 0; i < bn; i++)
			scanf("%d", &b[i]);

		// merge sort
		while (p < an && q < bn) {		// p가 an보다 작은 동시에 q도 bn보다 작을때 반복
			if (a[p]<b[q]) {			// a[p]가 b[q]보다 작으면
				printf("%d ", a[p]);	// a[p] 출력
				p++;					// p+1
			}
			else {						// a[p]가 b[q]보다 클때
				printf("%d ", b[q]);	// b[q] 출력
				q++;					// q+1
			}
		}
		// p 또는 q가 an 또는 bn의 값을 초과해서 위 반복문을 빠져나오면
		// 남은 원소들을 그냥 출력
		while (p < an) {
			printf("%d ", a[p]);
			p++;
		}
		while (q < bn) {
			printf("%d ", b[q]);
			q++;
		}

		return 0;
	}

 

필자는 이 문제를 통해 병합정렬의 원리와 문법을 익혔다.

문제의 난이도가 높아질수록 시간제한이 걸림돌이 된다는것 또한 익혔다.