문제
정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.
출력
첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.
출처
- 문제를 만든 사람: baekjoon
이번 문제 역시 5년 전에 풀었던 문제입니다.
지금보면 굉장히 간단한 문제이고, python과 같은 라이브러리가 넘치는 언어를 활용해서 푼다면
금방 풀 수 있는 문제일 것 같네요.
하지만, 5년전의 저는 아무것도 모르는 초짜였기 때문에 C언어와 java로 문제해결을 시도한 모습입니다.
그렇게 바로 성공했으면 좋았겠지만, java로 풀었을때는 시간초과의 역풍을 맞았네요.
먼저, java로 풀었던 코드를 공개하겠습니다.
아마 스튜디오에서 이미 풀어보고 정답을 제출했을 것이니 알고리즘은 맞겠지만
문제에서 제시하는 시간 제한을 초과한 것이겠지요
import java.util.Scanner;
import java.util.Vector;
public class Main {
public int partition(int[] a, int left, int right) {
int last = a[right];
int i = left;
int j = right - 1;
int temp;
while (i <= j) {
while (a[i] < last)
i++;
while (a[j] >= last) {
j--;
if (j == -1) // -1 인덱스 참조 오류.
break;
}
if (i < j) {
temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
temp = a[i];
a[i] = last;
a[right] = temp;
return i;
}
public void quickSort(int[] a, int left, int right) {
int x;
if (left < right) {
x = partition(a, left, right);
quickSort(a, left, x - 1);
quickSort(a, x + 1, right);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Main M = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int arr[] = new int[n+m];
for(int i = 0 ; i < n+m ; i++){
arr[i] = in.nextInt();
}
M.quickSort(arr,0,n+m-1);
int num = 0;
for(int i = 0 ; i < n+m ; i++){
if(num != arr[i])
System.out.print(arr[i]+ " ");
num = arr[i];
}System.out.println();
}
}아마 이때 대학교 2학년 시절이고, 당시 알고리즘 수업에서 퀵 소트를 배우고 있던 과정이라
퀵소트를 사용해서 풀려고 노력했던 것 같습니다.
정말 엄청난 노력이었던 것 같지만, 문제에서 원하는 것은 이런 고급 알고리즘은 아니었습니다.
아래의 C언어로 작성한 정답 코드를 보겠습니다.
#include<cstdio>
int a[1000000];
int b[1000000];
int c[1000000];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i = 0 ; i < n ; i++)
scanf("%d",&a[i]);
for(int i = 0 ; i < m ; i++)
scanf("%d",&b[i]);
int i = 0, j = 0, k = 0;
while(i< n && j < m){
if(a[i] > b[j]) c[k++] = b[j++];
else c[k++] = a[i++];
}
while(i < n) c[k++] = a[i++];
while(j < m) c[k++] = b[j++];
for(int l = 0 ; l < k ; l++)
printf("%d ",c[l]);
printf("\n");
}포인터를 열심히 이용해서 알고리즘 코드를 작성하신 것이 보이시나요?
a와 b의 배열 값을 받고, c 배열에 값을 넣어주면서
서로의 값을 비교하면서 넣어주는 간단한 알고리즘이었습니다.
정렬 알고리즘은 코딩테스트에서 자주 등장하기 때문에
쉽게 출제되는 경우가 많이 있는데요
자주 등장하느 정렬 알고리즘 정도는 암기하시고 혹은 많이 풀어보시고 가시는 것이 큰 도움이 됩니다.
이상 다이어릿이었습니다. 감사합니다.
