글 읽기 - 도와주십시오... 답을 못찾겟습니다...

john6014 7년 전 0

코드가 좀 더럽긴한데요.. 메인을 제외한 소스는 퀵 정렬 공부하고 스스로 짜보느라 추가된 정렬 소스들이구요

제가 생각하는 예제들로는 정상적인 값이 나오는데 어디서 틀리는건지 모르겟습니다...

// 11946 번 문제 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)
typedef struct _SCORE
{
	int team;
	int * solve; // 해결한 문제 여부를 확인 
	int time; // 총 걸린 시간
	int complete; // 해결한 총 문제 개수 
}SCORE;

void CompleteSort(SCORE Score[], int start, int end, int problem);
void TimeSort(SCORE Score[], int start, int end, int problem);
void NumberSort(SCORE Score[], int start, int end, int problem);

int main()
{
	SCORE * Score;
	int Team, Problem, count; // 팀 수 , 문제 수 , 채점 개수 
	int i, index;
	int S, T, P; // 각 줄의  입력에 대한 시간 , 팀 번호 , 문제 번호  
	char result[4];

	scanf("%d%d%d", &Team, &Problem, &count);

	Score = (SCORE*)malloc(sizeof(SCORE) * (Team + 1));

	for (i = 1; i <= Team; i++)
	{
		Score[i].team = i;
		Score[i].solve = (int*)calloc(Problem + 1, sizeof(int));
		Score[i].time = 0;
		Score[i].complete = 0;
		/*
		calloc -> malloc 과 달리 동적할당한 영역을 자동으로 0 으로 초기화
		=> calloc( 개수 , 크기 )
		*/
	}

	for (i = 0; i < count; i++)
	{
		scanf("%d%d%d%s", &S, &T, &P, result);

		if (!strcmp(result, "AC"))
		{
			if (Score[T].solve[P] != -1)
			{
				Score[T].time += S + Score[T].solve[P] * 20;
				Score[T].solve[P] = -1;
				Score[T].complete++;
			}
		}
		else
			if (Score[T].solve[P] != -1)
				Score[T].solve[P]++;
		
	}

	CompleteSort(Score, 1, Team, Problem); // complete 에 따른 내림차순 정렬 

	count = 0;

	for (i = 1; i <= Team; i++)
	{
		if (Score[i].complete == Score[i + 1].complete && count == 0)
		{
			index = i;
			count++;
		}
		else if (Score[i].complete == Score[i + 1].complete && count != 0)
			count++;
		else if (Score[i].complete != Score[i + 1].complete && count != 0)
		{
			TimeSort(Score, index, index + count, Problem);
			count = 0;
		}
	}

	count = 0;

	for (i = 1; i <= Team; i++)
	{
		if (Score[i].time == Score[i + 1].time && Score[i].complete == Score[i + 1].complete && count == 0)
		{
			index = i;
			count++;
		}
		else if (Score[i].time == Score[i + 1].time && Score[i].complete == Score[i + 1].complete && count != 0)
			count++;
		else if (Score[i].time != Score[i + 1].time && Score[i].complete != Score[i + 1].complete && count != 0)
		{
			NumberSort(Score, index, index + count, Problem);
			count = 0;
		}
	}

	for (i = 1; i <= Team; i++)
		printf("%d %d %d\n", Score[i].team, Score[i].complete, Score[i].time);

	free(Score);
	return 0;
}

void CompleteSort(SCORE Score[], int start, int end, int problem)
{
	int i, pivot, L, R, Teamtemp, Timetemp, *Solvetemp;

	Solvetemp = (int*)malloc(sizeof(int) * (problem + 1));

	pivot = Score[start].complete;	L = start;	R = end;
	Teamtemp = Score[start].team; Timetemp = Score[start].time;

	for (i = 1; i <= problem; i++)
		Solvetemp[i] = Score[start].solve[i];

	while (start < end)
	{
		while (pivot >= Score[end].complete && start < end) end--;

		if (start != end)
		{
			Score[start].complete = Score[end].complete;
			Score[start].team = Score[end].team;
			Score[start].time = Score[end].time;

			for (i = 1; i <= problem; i++)
				Score[start].solve[i] = Score[end].solve[i];

			start++;
		}

		while (pivot <= Score[start].complete && start < end) start++;

		if (start != end)
		{
			Score[end].complete = Score[start].complete;
			Score[end].team = Score[start].team;
			Score[end].time = Score[start].time;

			for (i = 1; i <= problem; i++)
				Score[end].solve[i] = Score[start].solve[i];

			end--;
		}
	}

	Score[start].complete = pivot;
	Score[start].time = Timetemp;
	Score[start].team = Teamtemp;

	for (i = 1; i <= problem; i++)
		Score[start].solve[i] = Solvetemp[i];

	free(Solvetemp);

	pivot = start;
	start = L;
	end = R;

	if (pivot > start) CompleteSort(Score, start, pivot - 1, problem);
	if (pivot < end)	 CompleteSort(Score, pivot + 1, end, problem);
}

void TimeSort(SCORE Score[], int start, int end, int problem)
{
	int i, pivot, L, R, Teamtemp, Completetemp, *Solvetemp;

	Solvetemp = (int*)malloc(sizeof(int) * (problem + 1));

	pivot = Score[start].time;	L = start;	R = end;
	Teamtemp = Score[start].team; Completetemp = Score[start].complete;

	for (i = 1; i <= problem; i++)
		Solvetemp[i] = Score[start].solve[i];

	while (start < end)
	{
		while (pivot <= Score[end].time && start < end) end--;

		if (start != end)
		{
			Score[start].complete = Score[end].complete;
			Score[start].team = Score[end].team;
			Score[start].time = Score[end].time;

			for (i = 1; i <= problem; i++)
				Score[start].solve[i] = Score[end].solve[i];

			start++;
		}

		while (pivot >= Score[start].time && start < end) start++;

		if (start != end)
		{
			Score[end].complete = Score[start].complete;
			Score[end].team = Score[start].team;
			Score[end].time = Score[start].time;

			for (i = 1; i <= problem; i++)
				Score[end].solve[i] = Score[start].solve[i];

			end--;
		}
	}

	Score[start].time = pivot;
	Score[start].complete = Completetemp;
	Score[start].team = Teamtemp;

	for (i = 1; i <= problem; i++)
		Score[start].solve[i] = Solvetemp[i];

	free(Solvetemp);

	pivot = start;
	start = L;
	end = R;

	if (pivot > start) TimeSort(Score, start, pivot - 1, problem);
	if (pivot < end)	 TimeSort(Score, pivot + 1, end, problem);
}

void NumberSort(SCORE Score[], int start, int end, int problem)
{
	int i, pivot, L, R, Completetemp, Timetemp, *Solvetemp;

	Solvetemp = (int*)malloc(sizeof(int) * (problem + 1));

	pivot = Score[start].team;	L = start;	R = end;
	Completetemp = Score[start].complete; Timetemp = Score[start].time;

	for (i = 1; i <= problem; i++)
		Solvetemp[i] = Score[start].solve[i];

	while (start < end)
	{
		while (pivot <= Score[end].team && start < end) end--;

		if (start != end)
		{
			Score[start].complete = Score[end].complete;
			Score[start].team = Score[end].team;
			Score[start].time = Score[end].time;

			for (i = 1; i <= problem; i++)
				Score[start].solve[i] = Score[end].solve[i];

			start++;
		}

		while (pivot >= Score[start].team && start < end) start++;

		if (start != end)
		{
			Score[end].complete = Score[start].complete;
			Score[end].team = Score[start].team;
			Score[end].time = Score[start].time;

			for (i = 1; i <= problem; i++)
				Score[end].solve[i] = Score[start].solve[i];

			end--;
		}
	}

	Score[start].team = pivot;
	Score[start].time = Timetemp;
	Score[start].complete = Completetemp;

	for (i = 1; i <= problem; i++)
		Score[start].solve[i] = Solvetemp[i];

	free(Solvetemp);

	pivot = start;
	start = L;
	end = R;

	if (pivot > start) NumberSort(Score, start, pivot - 1, problem);
	if (pivot < end)	 NumberSort(Score, pivot + 1, end, problem);
}

yongjun18 7년 전 1

main함수에서 NumberSort 를 호출하기 전, 재정렬 범위를 정할 때 실수가 하나 있었던 것 같네요.

Score.time 와 Score.complete 둘 중 하나만 달라도 정렬 범위에서 벗어나야 합니다. 그 하나로 인해 둘 사이엔 정렬이 끝났기 때문이죠.

변경 전

else if (Score[i].time != Score[i + 1].time && Score[i].complete != Score[i + 1].complete && count != 0) {
NumberSort(Score, index, index + count, Problem);
count = 0;
}

변경 후

else if ((Score[i].time != Score[i + 1].time || Score[i].complete != Score[i + 1].complete) && count != 0) {
        NumberSort(Score, index, index + count, Problem);
       count = 0;
  }

john6014 7년 전 0

답변은 감사합니다만.

음.... 제 논리가 맞을 껍니다만... 위 조건 이 해결한 문제 개수와 총 걸린 시간이 동일하면 팀번호 순서대로 정렬하는 것이므로 || 을 주어지면 엉뚱하게 돌아갑니다..

문제는 그냥 제가 정렬 인덱스를 잘못 지정햇네요...

어찌됫든 감사합니다 ㅎㅎ

yongjun18 7년 전 1

음, 제 말은 해결한 문제 개수와 총 시간이 동일하면 팀번호 순서대로 정렬하는 것이므로

해결 개수와 총 시간이 동일하지 않으면 ( = 해결 개수와 총 시간 중 하나라도 다르면 ) count 값 증가를 그만 두고 팀번호순 정렬을 해야한다는 것이었습니다.

그러고보니 바로 위에서 해결 개수와 총 시간이 동일한 경우의 수를 모두 체크 했으니

else if (count != 0) {
        NumberSort(Score, index, index + count, Problem);
       count = 0;
  }

위 코드로도 맞았습니다! 뜨네요.

아무튼 푸셨다니 다행입니다.

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

문제

문제

출처

ICPC

도와주십시오... 답을 못찾겟습니다...

john6014 7년 전 0

yongjun18 7년 전 1

john6014 7년 전 0

yongjun18 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말