글 읽기 - 1181번 액세스 위반

pje5288v 2년 전 0

안녕하세요 코린이입니당

1181번 문제를 mergesort를 구현해서 풀어보려고 하는데

계속 액세스 위반이 뜨네요 ㅠㅠ

어디서 오류가 발생하는건지 좀 찾아주실 수 있을까요....ㅠㅠ

감사합니다!

#include <iostream>
#include <string>

using namespace std;

const int MAX=20000;
int tmp_order[MAX];


struct MyStruct {
	string word="";
	int len=0;
};

void mergesort(MyStruct*, int*, int, int);
void merge(MyStruct*, int*, int, int, int, int);

int main() {
	int N;
	cin >> N;

	MyStruct* input = new MyStruct[N];
	int* order = new int[N];
	string tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		input[i].word = tmp;
		input[i].len = (int)strlen(tmp.c_str());
	}

	mergesort(input, order, 0, N - 1);
	tmp = "";
	for (int i = 0; i < N; i++) {
		if (tmp == input[order[i]].word) continue;
		else {
			cout << input[order[i]].word << endl;
			tmp = input[order[i]].word;
		}
	}

	delete[] input;
	delete[] order;
	return 0;
}

void mergesort(MyStruct* A, int* arr, int start, int last) {
	if (last > start) {
		int mid = start + (last - start) / 2;
		mergesort(A, arr, start, mid);
		mergesort(A, arr, mid + 1, last);
		merge(A, arr, start, mid, mid+1, last);
	}
}

void merge(MyStruct* A, int* arr, int start1, int  last1, int start2, int last2) {
	int a = 0; int b = 0;
	while ((a < last1 - start1 + 1) && (b < last2 - start2 + 1)){
		if (A[arr[start1 + a]].len > A[arr[start2 + b]].len) {
			tmp_order[a + b] = arr[start2 + b]; b++;
		}
		else if (A[arr[start1 + a]].len == A[arr[start2 + b]].len) {
			if (A[arr[start1 + a]].word > A[arr[start2 + b]].word) {
				tmp_order[a + b] = arr[start2 + b]; b++;
			}
		}
		else {
			tmp_order[a + b] = arr[start1 + a]; a++;
		}
	}
	if (a == last1 - start1 + 1) {
		while (b < last2 - start2 + 1) {
			tmp_order[a + b] = arr[start2 + b]; b++;
		}
	}
	else {
		while (a < last1 - start1 + 1) {
			tmp_order[a + b] = arr[start1 + a]; a++;
		}
	}

	for (int i = 0; i < a + b; i++) {
		arr[start1 + i] = tmp_order[i];
	}
}

zenith82114 2년 전 1

merge 함수에서 두 단어 길이가 같으면 word를 비교해서

뒤쪽(start2 + b)에 있는 단어가 먼저면 뒤쪽 단어가 tmp_order[a + b]에 들어가네요. 좋습니다.

근데 앞쪽(start1 + a)이 먼저거나 둘이 똑같을 때는 어떻게 하죠?

pje5288v 2년 전 1

하찮은 질문 답글 달아주셔서 감사합니당 ㅠㅠ

해당부분이랑 빼먹은 order초기화ㅠㅠ 고치니까 해결됐습니다!

감사합니다! 이 댓글이 전달되는건지는 모르지만...

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

문제

문제

출처

ICPC

1181번 액세스 위반

pje5288v 2년 전 0

zenith82114 2년 전 1

pje5288v 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말