백준 20920: 영단어 암기는 괴로워(C언어)

20920번: 영단어 암기는 괴로워

문제

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다.

그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다.

화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다.

화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다.

(1≤ N ≤100000, 1≤ M ≤10)

둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

출력

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

문제풀이

위의 내용을 정리해보면

1. N과 M값을 입력받는다.

2. 문자를 입력받는다.

3. 문자열이 M과 같거나 큰지 체크하고 값을 배열에 넣어준다.

4. 문자열을 문자열의 길이와 사전순으로 먼저 정렬을 해준다.

5. 정렬된 배열에서 같은 문자열의 개수에 따라 개수를 세주고, 겹치는 문자열을 제거한다.

6. 같은 문자열의 개수가 큰 순서대로 다시 정렬을 해준다.

 

처음에는 해시테이블로 정렬을 해주며 같은 문자열은 저장을 안하고 개수만 늘려주는 식으로 저장을 해줬다.

다음에 저장된 값들을 다시 배열로 옮겨주고 조건에 맞춰서 정렬을 해줬는데 값은 제대로 나오지만 시간 초과가 나와서 처음부터 다시 짰다.

병합 정렬은 이전부터 많이 다뤄왔기 때문에 부가 설명은 안하고, 다른 핵심적인 부분만 설명하겠다.

 

먼저 compare 함수이다. compare 함수는 두 차례 사용된다. 처음은 flag 값이 1로 들어왔을 경우 if문을 실행해주면서 탈출하게 된다.

if 안의 코드 용도는 먼저 문자열 길이를 비교해서 앞에가 길면 1을 반환 아니면 0을 반환하고 만약 같은 값일 경우 while 을 실행한다.

while 안의 코드 용도는 문자열 자체가 같은 문자열인지 비교하는 역할을 한다.

맨 앞 인덱스부터 차례대로 검사하면서 다를 경우 그 즉시 반환값을 줬다. 시간을 단축하기 위해서 strcmp 대신 사용해 줬다.

int compare(INFO* a, INFO* b, int flag) {
	int i = 0;
	if (flag) {
		if (a->len > b->len) return 1;
		else if (a->len < b->len) return 0;
		
		while (a->name[i]) {
			if (a->name[i] < b->name[i]) return 1;
			else if (a->name[i] > b->name[i]) return 0;
			i++;
		}
		return 1;
	}
	if (a->count >= b->count) return 1;
	return 0;
}

 

다음은 main 함수 안의 while 인데, 중복된 문자열을 제거해주고 개수를 증가시키기 위해서 사용했다.

i의 값은 앞의 비교 대상 index의 위치이고, next는 뒤의 비교 대상 index의 위치이다.

if 안의 값이 만약 비교 대상끼리 서로 값이 다를 경우에 앞의 내용을 저장해놓을 배열에 저장하는 식으로 저장하고, i의 값과 next의 값을 변경해주는 방식이다. 그리고 값이 같다면 개수를 증가해주는 방식이다.

 

	int i = 0, next = 1, sortnum = 0; 
	while (i < num) {
		if (strcmp(sorted[i].name, sorted[next].name)) {
			info[sortnum++] = sorted[i];
			i = next;
			next = i + 1;
			continue;
		}
		else sorted[i].count++;
		next++;
	}

최종코드

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

typedef struct _INFO{
	char name[11];
	int count;
	int len;
}INFO;

int compare(INFO* a, INFO* b, int flag) {
	int i = 0;
	if (flag) {
		if (a->len > b->len) return 1;
		else if (a->len < b->len) return 0;
		
		while (a->name[i]) {
			if (a->name[i] < b->name[i]) return 1;
			else if (a->name[i] > b->name[i]) return 0;
			i++;
		}
		return 1;
	}
	if (a->count >= b->count) return 1;
	return 0;
}

void merge_sort(INFO a[], INFO sorted[], int m, int mid, int n, int flag) {
	int i = m;
	int j = mid + 1;
	int k = m;

	while (i <= mid && j <= n) {
		if (compare(&a[i], &a[j], flag)) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	if (i > mid) {
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			sorted[k] = a[t];
			k++;
		}
	}

	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];
		sorted[t] = a[t];
	}
	return;
}

void merge(INFO a[], INFO sorted[], int m, int n, int flag) {
	if (m < n) {
		int mid = (m + n) / 2;
		merge(a, sorted, m, mid, flag);
		merge(a, sorted, mid + 1, n, flag);
		merge_sort(a, sorted, m, mid, n, flag);
	}
	return;
}

int main() {
	int n, m, num = 0;
	char temp[11];
	scanf("%d%d", &n, &m);
	
	INFO* info = (INFO*)malloc(sizeof(INFO) * n);
	INFO* sorted = (INFO*)malloc(sizeof(INFO) * n);

	for (int i = 0; i < n; i++) {
		scanf("%s", temp);
		int len = strlen(temp);
		if (len >= m) {
			strcpy(info[num].name, temp);
			info[num].len = len;
			info[num].count = 1;
			sorted[num] = info[num];
			num++;
		}
	}
	merge(info, sorted, 0, n - 1, 1);

	int i = 0, next = 1, sortnum = 0; 
	while (i < num) {
		if (strcmp(sorted[i].name, sorted[next].name)) {
			info[sortnum++] = sorted[i];
			i = next;
			next = i + 1;
			continue;
		}
		else sorted[i].count++;
		next++;
	}
	merge(info, sorted, 0, sortnum - 1, 0);
	for (int i = 0; i < sortnum; i++) {
		printf("%s\n", info[i].name);
	}
    	free(info);
    	free(sorted);
}