글 읽기 - 구조체, 머지소트를 이용했는데 안됩니다.

20183016 5년 전 0

먼저 테스트 케이스입니다.

input

input

10
aaaaaaaa
aaaaaaab
aaaaaaca
aaaaaaaaaaaaa
aaacdefaaaa
baaaa
baaaaaaaaaa
aaaaazaa
aaaacdsa
aaaaadd

output
a

output

baaaa
aaaaadd
aaaaaaaa
aaaaaaab
aaaaaaca
aaaaazaa
aaaacdsa
aaacdefaaaa
baaaaaaaaaa
aaaaaaaaaaaaa

구조체, 머지소트를 이용. 정렬 후 중복은 제거함수로 제거했습니다. 하지만 안됩니다..ㅜㅜㅜ

제가 생각가능한 대부분 테스트케이스는 문제에 만족합니다.

하지만 틀렸다고 나와서 반례가 있는건지.... 잘못 코딩한건지 모르겠습니다.

제가 생각해낸 구현 프로세스 :

문자열과 그 문자열의 길이를 한 구조체 내에서 정의
중복포함 길이 먼저 머지소트로 정렬
길이가 같을시 사전순으로 머지
머지소트 종료후 중복 제거
출력

이렇게 제가 구현했습니다. 잘못 코딩한거 있으면 지적 부탁드립니다 ㅜㅜㅜ

피가 마릅니다ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

0프로도 안나오고 틀렸습니다 나옵니다.

(추가)

코드 수정했습니다.

채점하자마자 틀렸다고 하는데

왜 안되는지 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Arr
{
	char word[100];
	int len;
};

void MergeTwoArea(struct Arr arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;
	struct Arr * sortArr = (struct Arr *)malloc(sizeof(struct Arr)*(right + 1));
	int sIdx = left;
	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx].len<arr[rIdx].len)
			sortArr[sIdx] = arr[fIdx++];
		else if (arr[fIdx].len>arr[rIdx].len)
			sortArr[sIdx] = arr[rIdx++];
		else
		{
			// 길이가 같을시 사전 순 처리
			for (i = 0; i<arr[fIdx].len; i++)
			{
				if (arr[fIdx].word[i] < arr[rIdx].word[i])
				{
					sortArr[sIdx] = arr[fIdx++];
					break;
				}
				else if (arr[fIdx].word[i] > arr[rIdx].word[i])
				{
					sortArr[sIdx] = arr[rIdx++];
					break;
				}
			}

			if (i == arr[fIdx].len)
			{
				sortArr[sIdx] = arr[fIdx++];
			}

		}


		sIdx++;
	}

	if (fIdx>mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(struct Arr arr[], int left, int right)
{
	int mid;
	if (left<right)
	{
		mid = (left + right) / 2;
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		MergeTwoArea(arr, left, mid, right);
	}
}


int main()
{
	int i;
	int n;
	struct Arr * arr;
	scanf("%d", &n);

	// 구조체 배열 선언
	arr = (struct Arr *)malloc(sizeof(struct Arr)*n);


	for (i = 0; i<n; i++)
	{
		scanf("%s", arr[i].word);
		arr[i].len = strlen(arr[i].word);
	}

	MergeSort(arr, 0, n - 1);

	printf("%s\n", arr[0].word);
	for (i = 1; i<n; i++)
	{
		if (strcmp(arr[i].word, arr[i - 1].word))
			printf("%s\n", arr[i].word);
	}

	free(arr);
	return 0;
}

indioindio 5년 전 1

96번째 줄의 while(strcmp(arr[i].word,arr[i+1].word)==0)

i가 arr의 범위 밖을 참조하는 경우가 있네요.

20183016 5년 전 0

답변 주셔서 정말 감사합니다. 지적해 주신 중복 제거 함수인 overlapErase를 수정해봤습니다. 역시 안되네여...

제일 수상한게 0%도 가지않고 "틀렸습니다"가 뜨는건데 좀 더 고민해봐야겠네요

void overlapErase(struct Arr arr[], int * pn)
{
	int i;
	int end = *pn;
	int cnt = 1;
	struct Arr * output = (struct Arr *)malloc(sizeof(struct Arr)*(*pn));
	
	output[0] = arr[0];
	for (i = 1; i < end; i++)
	{
		if (strcmp(arr[i].word, arr[i - 1].word))
			output[cnt++] = arr[i];
		else    //arr[i].word와 arr[i-1].word가 중복일때
		{
			(*pn)--;
		}
	}

	for (i = 0; i < cnt; i++)
		arr[i] = output[i];
	free(output);
}

20183016 5년 전 0

사전 순 정렬 코드를 strcmp로 했더니 해결했습니다.

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

문제

문제

출처

ICPC

구조체, 머지소트를 이용했는데 안됩니다.

20183016 5년 전 0

indioindio 5년 전 1

20183016 5년 전 0

20183016 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말