7701

static vector<string> table[51];
static char buf[64];
static string dummy("0");

static void solution(void)
{
	int N, max_len = 0, len;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		scanf("%s", buf);
		len = strlen(buf);
		table[len].push_back(buf);
		if (len >= max_len)
			max_len = len;
	}

	for (int i = 1; i <= max_len; i++)
	{
		vector<string> &cur = table[i];
		if (cur.empty())
			continue;

		string &priv = dummy; //dummy string,
		int size = cur.size();
		sort(cur.begin(), cur.end());	
		for (int idx = 0; idx < size; idx++)
		{
			string &cs = cur[idx];
			if (priv != cs)
				printf("%s\n", cs.data());
			priv = cs;
		}
		cur.clear();
	}
}

이번 문제에서는 N은 최대 2만 까지 주어진다. 그래서 cin 보다 scanf로 입력을 받는 것이 낫고,

마찬가지로 출력도 cout보다 printf가 낫다.

 

먼저 문자열의 최대 길이는 50이라고 문제에서 주어졌다. 그래서 이를 토대로 먼저 table을 관리할 벡터 배열을 전역으로 둔다.(우선순위는 길이가 작은 순이 먼저 이기 때문이다.)

그래서 입력받은 문자열의 길이를 인덱스로 하여 table의 문자열을 저장하고 뒤이어 전체 문자열의 최대 길이를 찾는다.

이는 두번째 반복문에서 최악의 경우 50까지 반복하지 않기 위함이다.

 

두번째 반복문에서는 문자열의 길이 1부터 시작하여 table을 점검한다.

없으면 당연히 볼 필요가 없기에 넘어가고 있으면 먼저 정렬을 해야한다.

정렬은 디폴트로 오름차순으로 되어있기에 달리 비교함수를 작성하여 넘길 필요는 없다.

그래서 정렬된 후에는 단순히 출력을 하면 되는데 여기서 한가지 중요한 조건은 동일한 이름은 한번만 출력해야 한다는 것이다.

이를 해결하기 위해 이전 문자열을 저장 할 필요가 있다. 왜냐하면 현재 참조하는 벡터는 이미 정렬되어 있기 때문이다.

 

//

사실 처음에는 vector 가 아닌 list로 해보았는데, list는 sort함수를 이용할 수 없었다. 

생각해보니 표준 라이브러리의 정렬은 보통 퀵정렬로 구현된다고 알고있어서 이는 당연한 결과 인 것 같다.