[백준_C언어] 1920: 수 찾기

✅Try 1 : 먼저 A배열 정렬하고 이진탐색 반복

/*1920번--수 찾기*/
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int i, j;
  int N;  //요소 개수
  int *A; //배열 이름A
  int *B; //배열 이름B
  int M;
  scanf("%d", &N);  //N 입력
  A = calloc(N, sizeof(int));
  //A 요소 입력받기
  for(i=0; i<N; i++)
  {
    scanf("%d", &A[i]);
  }

  //A 정렬
  for(i=0; i<N-1; i++)
  {
    j = i;
    while(j>=0){
      if(A[j] > A[j+1]){
        int temp = A[j];
        A[j] = A[j+1];
        A[j+1] = temp;
      }
      j--;
    }
  }

  scanf("%d", &M);  //M 입력받기
  B = calloc(M, sizeof(int));
  for(i=0; i<M; i++)
  {
    scanf("%d", &B[i]);
  }

  //이진탐색
  int pl = 0; //검색 범위 맨 앞 인덱스
  int pr = N-1; //검색 범위 맨 끝 인덱스
  int pc;   //검색 범위 중간 인덱스

  for(i=0; i<M; i++)
  {
    while(pl<=pr){
      pc = (pl+pr)/2;
      if(A[pc] == B[i])
        printf("1\n");  //검색성공
        break;
      else if(A[pc] < B[i])  //key값이 더 크면
        pl = pc + 1;
      else if(A[pc] > B[i]) //key값이 더 작으면
        pr = pc - 1;
      else//검색 실패
      {
        printf("0\n");
        break;
      }
    } 
  }

  free(A);
  free(B);

  return 0;
}

🔺문제: 이진탐색 반복이 안되고 break때문에 멈춘다.

 

✅Try 2: 함수로 만들고 return값을 0과 1로 

/*1920번--수 찾기*/
#include <stdio.h>
#include <stdlib.h>

int binarySerarch(int a[], int key, int n)
{
  //이진탐색
  int pl = 0; //검색 범위 맨 앞 인덱스
  int pr = n-1; //검색 범위 맨 끝 인덱스
  int pc;   //검색 범위 중간 인덱스

  while(pl<=pr){
    pc = (pl+pr)/2;
    if(a[pc] == key){
      return  1;   //검색 성공
    }
    else if(a[pc] < key)  //key값이 더 크면
      pl = pc + 1;
    else if(a[pc] > key) //key값이 더 작으면
      pr = pc - 1;
    else//검색 실패
      return 0;
  } 
}

int main(void) {
  int i, j;
  int N;  //요소 개수
  int *A; //배열 이름A
  int *B; //배열 이름B
  int M;
  scanf("%d", &N);  //N 입력
  A = calloc(N, sizeof(int));
  //A 요소 입력받기
  for(i=0; i<N; i++)
  {
    scanf("%d", &A[i]);
  }

  //A 정렬
  for(i=0; i<N-1; i++)
  {
    j = i;
    while(j>=0){
      if(A[j] > A[j+1]){
        int temp = A[j];
        A[j] = A[j+1];
        A[j+1] = temp;
      }
      j--;
    }
  }

  scanf("%d", &M);  //M 입력받기
  B = calloc(M, sizeof(int));
  for(i=0; i<M; i++)
  {
    scanf("%d", &B[i]);
  }

  for(i=0; i<M; i++)
  {
    printf("%d\n", binarySerarch(A, B[i], N));
  }
  

  free(A);
  free(B);

  return 0;
}

🔺문제: 띠용 5라는 의문의 값이 튀어나옴..뭐가 문제인지 찾다가 while문 밖에 빠져나왔을 경우에도 return 0을 해줘야 함을 깨달음

 

✅Try 3: while문 빠져나왔을 때도 return 0 챙겨주기

/*1920번--수 찾기*/
#include <stdio.h>
#include <stdlib.h>

int binarySerarch(int a[], int key, int n)
{
  //이진탐색
  int pl = 0; //검색 범위 맨 앞 인덱스
  int pr = n-1; //검색 범위 맨 끝 인덱스
  int pc;   //검색 범위 중간 인덱스
  int result; //탐색결과 반영

  while(pl<=pr){
    pc = (pl+pr)/2;
    if(a[pc] == key)
      return  1;   //검색 성공
    else if(a[pc] < key)  //key값이 더 크면
      pl = pc + 1;
    else if(a[pc] > key) //key값이 더 작으면
      pr = pc - 1;
    else//검색 실패
      return 0;
  }
  return 0;
}

int main(void) {
  int i, j;
  int N;  //요소 개수
  int *A; //배열 이름A
  int *B; //배열 이름B
  int M;
  scanf("%d", &N);  //N 입력
  A = calloc(N, sizeof(int));
  //A 요소 입력받기
  for(i=0; i<N; i++)
  {
    scanf("%d", &A[i]);
  }

  //A 정렬
  for(i=0; i<N-1; i++)
  {
    j = i;
    while(j>=0){
      if(A[j] > A[j+1]){
        int temp = A[j];
        A[j] = A[j+1];
        A[j+1] = temp;
      }
      j--;
    }
  }

  scanf("%d", &M);  //M 입력받기
  B = calloc(M, sizeof(int));
  for(i=0; i<M; i++)
  {
    scanf("%d", &B[i]);
  }

  for(i=0; i<M; i++)
  {
    printf("%d\n", binarySerarch(A, B[i], N));
  }
  

  free(A);
  free(B);

  return 0;
}

➡️결과

🔺문제: 출력은 잘 나왔는데 시간 초과가 나왔다. 머리 싸매다가 다른 사람 풀이 확인하니까 이진탐색과 퀵소트를 함께 사용함. 정렬할 때 시간 초과가 된 거 같았다.

✅퀵소트

C의 <stdlib.h>에 qsort()라는 함수로 이미 구현되어 있고, 형태는 다음과 같다.

qsort(정렬할 메모리 주소or배열이름, 정렬할 요소의 개수, 요소의 크기, 비교 함수)

마지막 파라미터인 비교함수 포인터에 대해 값을 비교하는 함수 하나를 만들어 줘야 한다.(오름차순/내림차순)

->오름차순: compare함수의 첫 번째 파라미터가 더 클 때 양수를 반환, 작을 때 음수를 반환, 같을 때 0을 반환하게 만든다.(내림차순은 반대로)

 

/*1920번--수 찾기*/
#include <stdio.h>
#include <stdlib.h>

int binarySerarch(int a[], int key, int n)
{
  //이진탐색
  int pl = 0; //검색 범위 맨 앞 인덱스
  int pr = n-1; //검색 범위 맨 끝 인덱스
  int pc;   //검색 범위 중간 인덱스

  while(pl<=pr){
    pc = (pl+pr)/2;
    if(a[pc] == key)
      return  1;   //검색 성공
    else if(a[pc] < key)  //key값이 더 크면
      pl = pc + 1;
    else if(a[pc] > key) //key값이 더 작으면
      pr = pc - 1;
    else//검색 실패
      return 0;
  }
  return 0;
}
// 퀵 소트에서 사용할 비교함수 
int cmp(const void* a, const void* b) 
{ 
  return *(int*)a > * (int*)b ? 1 : (*(int*)a < *(int*)b ? -1 : 0); 
}

int main(void) {
  int i, j;
  int N;  //요소 개수
  int *A; //배열 이름A
  int *B; //배열 이름B
  int M;
  scanf("%d", &N);  //N 입력
  A = calloc(N, sizeof(int));
  //A 요소 입력받기
  for(i=0; i<N; i++)
  {
    scanf("%d", &A[i]);
  }


  scanf("%d", &M);  //M 입력받기
  B = calloc(M, sizeof(int));
  for(i=0; i<M; i++)
  {
    scanf("%d", &B[i]);
  }

  qsort(A, N, sizeof(int), cmp);

  for(i=0; i<M; i++)
  {
    printf("%d\n", binarySerarch(A, B[i], N));
  }
  

  free(A);
  free(B);

  return 0;
}