백준 1181 단어정렬 C/C++

단어 정렬 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

112484

46788

34940

40.211%

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1 복사

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1 복사

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

using namespace std;





typedef struct
{
	char name[51];
	int size;
}user;


void MergeTwoArea(user*arr, int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	user* sortArr = (user*)malloc(sizeof(user) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx].size < arr[rIdx].size)
			sortArr[sIdx] = arr[fIdx++];
		else if(arr[fIdx].size > arr[rIdx].size)
			sortArr[sIdx] = arr[rIdx++];
		else
		{
			if (strcmp(arr[fIdx].name, arr[rIdx].name) < 0)
				sortArr[sIdx] = arr[fIdx++];
			else
				sortArr[sIdx] = arr[rIdx++];
		}
		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(user* 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);
	}
}



user arr[100001];
int main(void)
{
	int n;
	
	cin >> n;


	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].name;
		arr[i].size= strlen(arr[i].name);
	}

	MergeSort(arr, 0, n - 1);


	for (int i = 1; i <= n; i++)
	{
		
			if (strcmp(arr[i-1].name, arr[i].name) != 0)
				cout << arr[i-1].name << "\n";
		
		
	}
	
	return 0;
}

 

여러 블로그 + 책의 글을 짬뽕했는데, 출처를 까먹었다.

 

우선 병합정렬은 '윤성우의 열혈 자료구조'에서 따왔다. 거기에 있는 소스코드로 병합정렬을 하는데, 구조체를 대상으로 병합정렬을 하려면, 구조체 이름에 맞게 매개변수를 조정해줘야한다. 

 

int-> 구조체명(user)

 

그리고 두 가지 추가된 조건이

1) 중복 제거

2) 동일 길이시 단어를 알파벳 순 출력

 

1)과 2)에 모두 strcmp를 썼는데, str을 크기 비교를 해주는 함수이다.

2)에서 이거가 있으면 알파벳 순으로 정렬하는 것을 직접 구현하지 않아도 알아서 해주는 듯하다. 직접 구현 해보고 싶었지만 머리가 딸려서 못했다.

 

1)에서는 이 부분이 같으면 중복된 값인데, 이 값은 출력을 안하는 것으로 하면 된다.