글 읽기 - 카운트 정렬 이용해서 풀어봤는데 3퍼센트에서 막혀요 ㅠㅠ

kaiose 6년 전 0

sum 값도 long 으로 제대로 줬는데 뭐가 문제일까요

k 개 만큼 정렬해서 중앙값 빼내는 형식으로 했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <math.h>
#include <string.h>

int ctSort(int* arrT, int K, int d) {
	int* arr = new int[K];
	memcpy(arr, arrT, sizeof(int)*K);
	int degree = 10;
	int* temp = new int[K];
	memset(temp, 0, sizeof(int)*K);
	int result = 0;
	for (int p = 0; p < d; p++) {
		int count[10] = { 0 };
		int num = (int)pow(10, p);
		for (int i = 0; i < K; i++) { count[(arr[i] % (num * 10)) / num]++; }
		for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; }
		for (int i = K - 1; i >= 0; i--) {
			temp[count[(arr[i] % (num * 10)) / num] - 1] = arr[i];
			count[(arr[i] % (num * 10)) / num]--;
		}
		degree *= 10;
		for (int i = 0; i < K; i++) {
			arr[i] = temp[i];
		}
	}
	result = temp[(K + 1) / 2 - 1];
	delete[] arr;
	delete[] temp;
	return result;
}
int main() {
	int N; // 갯수
	int K; // 연속수갯수
	scanf("%d%d", &N, &K);
	long sum = 0;
	int* temp = new int[K];
	memset(temp, 0, sizeof(int)*K);
	int max = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &temp[i%K]);
		if (max < temp[i%K]) { max = temp[i%K]; }
		int count = 0;
		while (true) {
			if (max / (int)pow(10, count) == 0) break;
			count++;
		}// 진법
		if (i >= K - 1) {
			sum += ctSort(temp, K, count); //카운트소팅
		}
	}
	printf("%d", sum);
	delete[] temp;
	return 0;
}

djm03178 6년 전 1

%d는 int형을 출력하는 서식문자이고, long형을 출력하려면 %ld로 해야 됩니다. 그리고 long도 4바이트일 가능성이 높다고 봅니다. long long형과 서식 문자 %lld를 써보세요.

kaiose 6년 전 0

좋지만 시간초과나버렸네요 소팅하는 문제가 아닌가..? 카운트소팅이 제일 시간 빠를 꺼 같았는데 말이죠.. 차수만안다면

차수구하는거뺴고 어차피 6만대까지 니까 6개 넣고 돌려도 똑같네요

irishw 6년 전 1

매번 정렬하면 시간초과 날거에요 다른 방법을 고민해보세요.

자료구조에 트리

세그먼트트리나, 펜윅트리 공부해보시면 좋을듯 합니다

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

문제

문제

출처

ICPC

카운트 정렬 이용해서 풀어봤는데 3퍼센트에서 막혀요 ㅠㅠ

kaiose 6년 전 0

djm03178 6년 전 1

kaiose 6년 전 0

irishw 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말