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

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

기억력 테스트 4

 

▶코드 작성

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

void quicksort(int **arr, int left, int right)//퀵정렬
{
    int L = left, R = right, *temp;
    int pivot = arr[(L + R) / 2][0];//arr배열의 중앙값
    while (L <= R)
    {
        while (arr[L][0] < pivot) L++;
        while (pivot < arr[R][0]) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (left < R) quicksort(arr, left, R);
    if (L < right) quicksort(arr, L, right);
}

void printResult(int **arr, int *ask, int n, int m)//숫자 몇번째인지 출력
{
    int left = 0, right = n - 1, L, R, num;
    int pivot;

    for (int i = 0; i < m; i++)
    {
        L = left;
        R = right;
        num = -1;
        while (L <= R)//이분탐색
        {
            pivot = (L + R) / 2;
            if (arr[pivot][0] > ask[i]) R = pivot - 1;
            else if (arr[pivot][0] < ask[i]) L = pivot + 1;
            else if (arr[pivot][0] == ask[i])//값을 찾으면
            {
                num = arr[pivot][1];//몇번째인지 대입
                break;
            }
        }
        printf("%d ", num);
    }
}

int main()
{
    int n, m, temp;
    int **arr;
    int ask[100000];

    scanf("%d", &n);

    arr = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++)
    {
        arr[i] = (int *)malloc(sizeof(int) * 2);
    }

    for (int i = 0; i < n; i++)//처음 숫자들 입력
    {
        scanf("%d", &arr[i][0]);
        arr[i][1] = i + 1;//몇번째인지
    }

    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", &ask[i]);//질문할 숫자들 입력

    quicksort(arr, 0, n - 1);//arr배열 퀵정렬

    printResult(arr, ask, n, m);//몇번째인지 출력

    for (int i = 0; i < n; i++) free(arr[i]);
    free(arr);

    return 0;
}

 

▶해석

처음 수들을 2차원 배열로 동적 할당하여 숫자와 그 번호를 입력받고 그다음 질문할 수들을 입력받았다. 퀵 정렬을 이용하여 처음 받은 수들을 정렬하고 printResult함수로 질문한 수들을 이분 탐색으로 찾아서 출력하였다. 다소 긴 코드라서 나중에 다시 한번 깔끔하게 해 봐야겠다.