코드업(codeup) 3002 : 기억력 테스트 3 C언어

▶문제 : 기억력 테스트 3 (codeup.kr)

기억력 테스트 3

 

▶코드 작성

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m;
    int *arr, *num;
    int left, right, mid;

    scanf("%d", &n);

    arr = (int *)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    scanf("%d", &m);

    num = (int *)malloc(sizeof(int) * m);

    for (int i = 0; i < m; i++)
    {
        scanf("%d", &num[i]);
    }

    for (int i = 0; i < m; i++)
    {
        left = 0;
        right = n - 1;
        while (left <= right)//이진 탐색
        {
            mid = (left + right) / 2;//중앙값을 구하기 위해
            if (num[i] < arr[mid])//중앙값보다 작다면
            {
                right = mid - 1;//오른쪽 배열자리수를 중앙값에서 더 작은 수로 설정
            }
            else if (num[i] > arr[mid])//중앙값보다 크면
            {
                left = mid + 1;//왼쪽 배열자리수를 중앙값에서 더 큰 수로 설정
            }
            else if (num[i] == arr[mid])//찾고자 하는 수를 찾았다면
            {
                break;//while문 종료
            }
        }
        if (num[i] == arr[mid])
        {
            printf("%d ", mid + 1);
        }
        else
        {
            printf("-1 ");
        }
    }

    free(arr);
    free(num);

    return 0;
}

 

▶해석

이진 탐색을 이용하여 변수 left right를 배열의 끝과 끝인 0과 n-1로 정하고 while문으로 중앙값인 mid를 left와 right를 이용해 구한 후, 찾고자 하는 값 num [i]과 오름차순 배열의 중앙값 arr [mid]를 비교해 num [i] 값이 작다면 오른쪽 값 right를 mid에서 -1 한 값으로 저장하여 다시 mid값을 구하고, num [i] 값이 작다면 왼쪽 값 left를 mid에서 +1 한 값으로 저장하여 다시 mid값을 구하고를 반복해 같은 값을 찾거나 못 찾아서 left> right가 되었을 때 while문 종료를 한다.