백준 1181번. 단어정렬 문제풀이와 해설

요새 '초라기 습격' 이란 문제를 풀어보고 있는데 시간제한으로 난이도가 장난 아니라서,

이런 저런 고민 아닌 고민을 하고 있습니다.

​

풀이에 성공하신 분들이 소스를 공개하긴 했지만 크레이는 어디까지나 혼자 힘으로 100% 이해해서 푸는 걸 목적으로 하기 때문에 며칠째 끙끙거리고 있습니다 ㅎㅎ

​

우선 쉬운 문제 풀어보면서 머리를 좀 식힐겸사~

​

단어정렬 문제 링크 주소는 아래와 같습니다.

​

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

​

이번 문제의 목적은 짧은 단어순 정렬, 동일한 글자수라면 알파벳순 정렬,

그리고 중복출력을 제거하는 부분인데요,

아주 간단한 방법으로 해결 가능합니다.

​

아래와 같은 단어 목록을 메모리에 저장할 때,

 

but
i
wont
hesitate

앞에 글자수를 2자리 붙이는 것이지요. 앞에 글자수 숫자가 붙었기 때문에 기본 정렬만 하면, 글자수 우선, 알파벳 나중으로 정렬이 되겠지요.

 

03but
01i
04wont
08hesitate

그리고 나서 C++의 정렬 기능을 사용하면 됩니다.

 

sort(s, s+n, comp);

이 때, comp 라는 함수가 하나 필요한데, 정렬을 어떤 방법으로 할지를 결정하는 것입니다. 사실 strcmp 라는 함수 하나만 사용하면 됩니다.

bool comp(char *s1, char *s2){
	return strcmp(s1, s2)<0;
}

이번 소스는 매우 짧습니다.

주석을 보고 참조해주시면 되겠습니다 :)

#include <algorithm>
#include <cstring>
using namespace std;

// 각 단어를 저장할 문자배열 포인트 20,000개
char *s[20000];

// 2개의 문장을 비교히여 크고 작음을 판단할 함수
bool comp(char *s1, char *s2){
	return strcmp(s1, s2)<0;
}

void Result()
{
	int n;	
	char tmp[51];
	
	// 단어 갯수를 입력
	scanf("%d", &n);

	// n개의 단어를 
	for(int i=0;i<n;++i)
	{	
		// 입력받고
		scanf("%s", tmp);
		// 메모리를 동적 할당
		// ( 문장길이 + 2글자(단어갯수) + 1글자('\0'문자) 
		// 단어 1개당 최대 53 글자 할당 필요
		s[i] = new char[strlen(tmp)+3];
		sprintf(s[i], "%02d%s", strlen(tmp), tmp);
	}	

	// C++의 정렬 기능을 사용합니다.
	// s 부터 s+n 포인터 목록까지
	// comp 함수가 정렬판단 조건 함수가 됩니다.
	sort(s, s+n, comp);

	// 이제 단어 목록을 n개 출력하는데,
	for(int i=0;i<n;++i)
	{
		// 바로 앞에 출력했던 단어와 똑같다면 출력하지 않습니다.
		if(i>0 && strcmp(s[i-1], s[i])==0)continue;
		// 출력할 때는 앞의 2자리 숫자는 빼고 출력합니다.
		printf("%s\n", &s[i][2]);
	}
}

int main()
{
	Result();
	return 0;
}