✅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;
}
'BOJ' 카테고리의 다른 글
백준 [C언어] 11729: 하노이 탑 이동 순서 (0) | 2022.01.28 |
---|---|
백준[C언어] 1966: 프린터 큐 (0) | 2022.01.26 |
백준[C언어] 1182: 부분수열의 합 (0) | 2022.01.26 |
백준[C언어] 1874: 스택 수열 (0) | 2022.01.25 |
[백준 C언어] 2805: 나무 자르기 (0) | 2022.01.19 |