문제
연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.
입력
첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.
출력
‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.
내 제출
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int arr_a[1000001], arr_b[1000001], copy[1000001];
void Mergesort(int left, int right) {
int mid = (left+right)/2;
if(left < right){
Mergesort(left, mid);
Mergesort(mid+1, right);
Mergetwoarea(left, mid, right);
}
}
void Mergetwoarea(int left, int mid, int right){
int fidx = left, ridx = mid+1;
int sidx = left, i;
while(fidx <= mid && ridx <= right) {
if(arr_a[fidx] > arr_a[ridx]){
copy[sidx] = arr_a[ridx++];
}
else{
copy[sidx] = arr_a[fidx++];
}
sidx++;
}
if(fidx > mid){
for(i=ridx; i <= right; i++){
copy[sidx] = arr_a[i];
sidx++;
}
}
else{
for(i=fidx; i <= mid; i++){
copy[sidx] = arr_a[i];
sidx++;
}
}
for(i=left; i <= right; i++){
arr_a[i] = copy[i];
}
}
int binarysearch(int left, int right, int num) {
while(left <= right) {
int mid = (left+right)/2;
if(num == arr_a[mid]) return 1;
else if(num < arr_a[mid]) {
right = mid - 1;
}
else if(num > arr_a[mid]) {
left = mid + 1;
}
}
return 0;
}
int main() {
int N, M, T;
int i, j;
scanf("%d", &T);
for(i=0; i < T; i++){
scanf("%d", &N);
for(j=0; j < N; j++){
scanf("%d", &arr_a[j]);
}
scanf("%d", &M);
for(j=0; j < M; j++){
scanf("%d", &arr_b[j]);
}
Mergesort(0, N-1);
for(j=0; j < M; j++){
printf("%d\n", binarysearch(0, N-1, arr_b[j]));
}
}
return 0;
}
이 문제는 이진 탐색과 합병 정렬을 이용해서 풀었다.
이진 탐색은 자주 사용한 탐색 방법인데, 합병 정렬은 어색할 것 같아서 조금 설명을 추가해본다.
합병 정렬이란 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
입력 배열을 같은 크기의 2개의 부분 배열로 분할하고, 부분 배열의 크기가 충분히 작을 때까지 순환을 통해 쪼개고, 정렬된 부분 배열들을 하나의 배열에 합병하는 형식으로 이루어진다.
보통 부분 배열의 크기가 충분히 작다 = 1개의 원소를 가진 배열이다.
합병 정렬로 입력받은 배열을 정리한 다음에 이진 탐색으로 숫자가 있는지 없는지를 확인한다.
열심히 다 짜고 생각난 건데, 아마 그냥 정렬 기능...을 이용하면 되지 않았을지...