글 읽기 - 무엇이 문제인지 반례를 찾을수가 없습니다.

kjp150 1년 전 1

처음에는 최빈값이 문제인 것 같아 최빈값 알고리즘을 계속 수정하였는데 계속 틀렸다고합니다.

그래서 이제는 최빈값은 문제 가없는 것같아 다른 분들이 올린 질문들을 보았는데

대부분 평균값에서 문제가 발생하시길래 저도 평균값을 구하는 알고리즘을 수정하였는데

어떠한 부분에서 반례가 발생하는지 몰라 도움을 구하고자 질문올립니다.

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

int compare(const void* a, const void* b) {
	return *(int*)a - *(int*)b;
}

int main() {
	// 중앙값을 구할때는 입력된수를 중복하지 않고 중앙에 있는 값을 구해야한다.-> 이러면 중복되는 값으로 인해서 중복되지 않는 수가 짝수개가
	// 된다면 1 1 2 3 4 5 6 이런식의 입력이면 중복을 제거하면 1 2 3 4 5 6 이다.
	// 1 2 3 4 5 6 에서는 중앙값을 구할수가 없다. 따라서 중복을 제거하면 안된다.
	// 최빈값이 여러개 일때는 두 번쨰로 작은 값을 출력한다.
	int n,avg=0,rvg=0,mid=0,val=0;
	float sum = 0;
	int count = 0;
	
	// 입력 받을 갯수를 입력 받는다.
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * (n + 2));
	int* arr_val = (int*)malloc(sizeof(int) * (8001));
	for (int i = 0; i < 8001; i++) {
		arr_val[i] = 0;
		// arr_val의 인덱스 i는 입력받은 수 +4000이다.
	}
	// 숫자를 입력받는다.
	// 입력 받을 때마다 sum에 누적해준다.
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		sum = sum + arr[i];
		arr_val[arr[i] + 4000]++;
	}
	count = arr_val[0];
	// 가장 작은 최빈값을 찾는 반복문
	for (int i = 0; i < 8001; i++) {
		if (count < arr_val[i]) {
			count = arr_val[i];
			val = i - 4000;
			// val은 가장 작은 최빈값이다.
			// count는 최빈값이 반복된횟수
			// 이 조건문은 최빈값이 발견되면 더이상 조건을 만족할수 없다. 등호가 없기 때문에
			// 또한 인덱스가 크기순으로 구성되어 있기 때문에 최빈값을 작은 수부터 찾으므로 
			// 처음 발견되면 최빈값은 당연히 가장 작은 최빈값이다.
		}
	}
	for (int i = 0; i < 8001; i++) {
		if (arr_val[i] == count && val < i - 4000) {
			val = i - 4000;
			break;
		}
	}
	float temp_avg = sum / (float)n;

	if (temp_avg - (int)temp_avg >= 0) {
		avg = temp_avg + 0.5;
	}
	else if (temp_avg - (int)temp_avg < 0) {
		avg = temp_avg - 0.5;
	}

	qsort(arr, n, sizeof(int), compare);
	
	mid = arr[(n-1)/2];
	rvg = arr[n - 1] - arr[0];
	printf("%d\n", avg);
	printf("%d\n", mid);
	printf("%d\n", val);
	printf("%d", rvg);
	free(arr);
	free(arr_val);
	return 0;
}

beawall 1년 전 1

1. 우선 특별한 이유가 없다면 float 대신 double을 쓰는걸 추천드리고,

2. 54번 줄의 조건식에서 등호를 빼는 게 맞는 것 같습니다. 저대로면 -3,-3,3 을 입력 받았을 때 0.5를 더하고 저장하게 되어 -1이 되어야 할게 0이 되어버립니다.

물론 이 경우 등호가 적용될 때 avg 변수를 temp_avg로 할당하는 else 문이 필요하겠죠

3. 최빈값 찾을때 33번줄 밑에 val=-4000 추가해야겠네요

kjp150 1년 전 0

조언해주신대로 수정하니 정답이 네요.

긴 코드글 읽고 조언해주셔서 감사합니다.

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

문제

문제

출처

ICPC

무엇이 문제인지 반례를 찾을수가 없습니다.

kjp150 1년 전 1

beawall 1년 전 1

kjp150 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말