글 읽기 - [C언어] 출력초과가 나옵니다.

chhs2131 3년 전 0

먼저 프로그램을 간단히 설명드리자면

1) 입력받은 문자열의 길이를 확인하여 저장합니다.

2) 문자열길이를 기준으로 퀵정렬을 진행합니다.

3) 동일한 길이를 가진 문자열이 있을 경우, 사전순으로 정렬합니다.

4) 정렬된 데이터를 출력합니다. (출력하려는 데이터가 이미 출력된 경우 그냥 넘어감)

채점중 출력초과가 나옵니다.

예제를 포함한 아래 테스트케이스 확인해보았습니다. 반례가 있을까요?

```
10
a
b
c
a
b
c
a
b
c
a
```

```
5
aaaaa
bcaaa
baaaa
baeee
eeee
```

```
6
a
b
ab
ba
aa
bb
```

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _word {
	int len;
	char c[50];
}word;


int compare(const void* a, const void* b) {
	int one = *(int *)a;
	int two = *(int *)b;

	return one - two;
}

int compare_string(const void* a, const void* b) {
	return strcmp((char *)a, (char *)b);
}

void qsort_string(word* arr, int start, int end) {
	int len = end - start + 1;
	char temp[20000][50];

	for (int i = 0; i < len; i++) {
		strcpy(temp[i], arr[start + i].c);
	}

	qsort(temp, len, sizeof(temp[0]), compare_string);
	for (int i = 0; i < len; i++) {
		strcpy(arr[start + i].c, temp[i]);
	}
}



int main(void) {
	// 변수선언 및 입력받기
	int n;
	word* word_input;
	scanf("%d", &n);

	word_input = (word *)malloc( sizeof(word) * n);
	for (int i = 0; i < n; i++) {
		scanf("%s", &word_input[i].c);
		word_input[i].len = strlen(word_input[i].c);
	}

	// 문자길이를 기준으로 퀵정렬
	qsort(word_input, n, sizeof(word), compare);

	// 동일한 길이의 문자가 있을 경우 정렬실행.
	int start = 0, end = 0, flag = 0;
	for (int i = 0; i < n - 1; i++) {
		if (word_input[i].len == word_input[i + 1].len) {
			if (flag == 0) {
				flag = 1;
				start = i;
			}
		}
		else if (flag == 1) {
			flag = 0;
			end = i;
			qsort_string(word_input, start, end);
		}

		if (flag == 1 && i == n - 2) {
			flag = 0;
			end = i + 1;
			qsort_string(word_input, start, end);
		}
	}

	// 출력 (중복검사 동시에 진행)
	printf("%s\n", word_input[0].c);
	if (n != 1) {
		for (int i = 1; i < n; i++) {
			if (compare_string(word_input[i].c, word_input[i - 1].c))
				printf("%s\n", word_input[i].c);
		}
	}
	
	return 0;
}

chhs2131 3년 전 0

해당 문제는 문자열(String)이 저장되는 변수가 작아서 발생했던 문제였습니다.

(문자열의 끝을 알리는 표시가 기록되지 못해, 다음 문자열까지 같이 출력됨.)

6번줄, 23번줄의 50을 51로 바꾸면 해결됩니다.

아래는 해당 반례입니다. (50개짜리 문자열)

aaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbaaaaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

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

문제

문제

출처

ICPC

[C언어] 출력초과가 나옵니다.

chhs2131 3년 전 0

chhs2131 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말