글 읽기 - 코드 오류를 못찾겠습니다...

lsch6214 1년 전 0

처음 카드로 입력 받는 배열을 오름차순 정리 이후 이진 탐색으로 문제를 해결하려고 했습니다.

중간 중간 출력문을 넣어서 어디가 잘못되는건지 파악을 하려고 몇 시간, 수십 차례를 할애했지만 못찾겠습니다..

문제는 binary_search 함수에서 if(arr[mid] == cardNumber) 일 때인데

예제 실행시 출력이 3 0 0 1 2 0 0 2 가 나와야하지만 어떠한 이유인지 3 0 0 3 2 0 0 2 가 나옵니다. 해당 if절에 출력문을 끼워 확실히 오류가 발생하는지는 확인하였지만 아무리 생각해봐도 왜 오작동이 나는지 당췌 모르겠습니다. 탈모 올거같습니다...

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);
void binary_search(int* arr, int cardNumber, int start, int end, int size, int* count);
int main() {
	int N, M, * card, *rank, * count;
	scanf("%d", &N);
	card = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
		scanf("%d", &card[i]);
	qsort(card, N, sizeof(int), compare);
	
	scanf("%d", &M);
	rank = (int*)malloc(sizeof(int) * M);
	count = (int*)malloc(sizeof(int) * M);
	
	for (int i = 0; i < M; i++) {
		scanf("%d", &rank[i]);
		count[i] = 0;
	}
	
	for (int i = 0; i < M; i++)
		binary_search(card, rank[i], 0, N - 1, i, count);
	for (int i = 0; i < M; i++)
		printf("%d ", count[i]);
    
    free(count);
    free(rank);
    free(card);
	return 0;
}
void binary_search(int* arr, int cardNumber, int start, int end, int size, int* count) {
	int left = start, right = end, mid;
	while (1) {
		mid = (left + right) / 2;
		if (arr[mid] == cardNumber) {
			count[size]++;
			binary_search(arr, cardNumber, 0, mid - 1, size, count);
			binary_search(arr, cardNumber, mid + 1, right - 1, size, count);
			break;
		}
		else if (arr[left] == cardNumber) {
			count[size]++;
			binary_search(arr, cardNumber, left + 1, right - 1, size, count);
			break;
		}
		else if (arr[right] == cardNumber) {
			count[size]++;
			binary_search(arr, cardNumber, 0, right - 1, size, count);
			break;
		}
		if (arr[mid] > cardNumber)
			right = mid - 1;
		else
			left = mid + 1;
		if (left >= right)
			break;
	}
}
int compare(const void *a, const void *b) {
	return *(int*) a - *(int*)b;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드 오류를 못찾겠습니다...

lsch6214 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말