1181. 단어 정렬

정렬을 이용하여 단어를 정렬하는 문제였다. 

정렬을 이용하는 가장 쉬운 문제였지만, 이 문제의 경우 퀵정렬을 사용할 경우 시간초과가 뜬다.

이에 유의해서 merge sort를 사용하였다. 시간은 딱맞았다. 

하지만, merge sort의 경우, 배열을 2배를 사용했기에 공간효율이 좋지 못한 것 같다. 

-런타임에러 : 배열의 크기를 선언할 때, 0을 하나 누락했었다.

- 시간초과 : 알고리즘을 수정하였다. quick -> merge sort로

#include<stdio.h>
#include<iostream>
using namespace std;
string list[20001];
void swap(int i, int j) {
	string temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}
int check_dictionary(string a, string b) {
	int i =0;
	while (i < a.length()) {
		if (a[i] < b[i])
			return 0;
		else if (a[i] > b[i])
			return 1;
		else
			i++;
	}
	return 0;
}
string arr2[20000];
void merge_sort(int left, int right) {
	int mid = (left + right) / 2;
	int k = left;
	int i = left;
	int j = mid + 1;
	while (i <= mid && j <= right) {
		if (list[i].length() > list[j].length())
			arr2[k++] = list[j++];
		else if (list[i].length() < list[j].length())
			arr2[k++] = list[i++];
		else {
			if (check_dictionary(list[i], list[j]))
				arr2[k++] = list[j++];
			else
				arr2[k++] = list[i++];
		}
	}
	int temp = i <= mid ? i : j;
	while (k <= right)
		arr2[k++] = list[temp++];
	while (left <= right) {
		list[left] = arr2[left];
		left++;
	}
}
void partition(int left, int right) {
	int mid = (left + right) / 2;
	if (left < right) {
		partition(left, mid);
		partition(mid + 1, right);
		merge_sort(left, right);
	}
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	int amount = 0;
	scanf("%d", &amount);
	for (int i = 0; i < amount; i++)
		cin>>list[i];
	partition(0, amount - 1);
	//quick_sort(0, amount-1);
	string before = "0";
	for (int i = 0; i < amount; i++) {
		if (before == list[i])
			continue;
		cout << list[i] << endl;
		before = list[i];
	}


	return 0;
}                         

 

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬