본문 바로가기
코딩과 알고리즘

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

728x90

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

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

풀이에 성공하신 분들이 소스를 공개하긴 했지만 크레이는 어디까지나 혼자 힘으로 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;
}

 

 

728x90
반응형