[백준 1181] 단어 정렬

1. string를 사용 ( 매우 쉬움 )

2. 구조체 안에 char배열 선언해서 해결하는 방법 ( 쏘쏘 )

3. string + unordered_set을 이용해서 같은 문자열 필터링 ( 속도 얼마 나올지 궁금해서 해본 것 )

 

1. string

#include <bits/stdc++.h>

using namespace std;

bool compare(const string& s1, const string& s2) {
	if (s1.size() == s2.size()) return s1 < s2;
	return s1.size() < s2.size();
}

string str[20001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> str[i];

	sort(str, str + n, compare);

	cout << str[0] << '\n';
	// 이전에 string과 같으면 출력 X
	for (int i = 1; i < n; ++i) if (str[i - 1] != str[i]) cout << str[i] << '\n';

	return 0;
}

2. 구조체 사용

#include <bits/stdc++.h>
using namespace std;

struct Word {
	// 문자열의 길이가 50을 넘지 않으므로 1Byte로도 표현 가능
	char size;
	char str[51];
};

bool compare(const Word& w1, const Word& w2) {
	if (w1.size == w2.size) for (int i = 0; i < w1.size; ++i) {
		if (w1.str[i] == w2.str[i]) continue;
		return w1.str[i] < w2.str[i];
	}
	return w1.size < w2.size;
}

Word word[20001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;

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

	sort(word, word + n, compare);

	cout << word[0].str << '\n';
	for (int i = 1; i < n; ++i) if (strcmp(word[i].str, word[i - 1].str)) cout << word[i].str << '\n';
	
	return 0;
}

이 코드는 운 좋게.. 1페이지에 등극했다..

재밌는 점은 printf를 쓰면 20ms가 나오고 cout을 쓰면 16ms가 나온다. fastio의 힘은 대단하다.

 

3. string + unordered_set

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;

bool compare(const string& s1, const string& s2) {
	if (s1.size() == s2.size()) return s1 < s2;
	return s1.size() < s2.size();
}

vector<string> vec;
unordered_set<string> us;
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;

	string str;
    
	for (int i = 0; i < n; ++i) {
		cin >> str;
		// 이미 존재하는 문자열인지 확인, 없다면 추가 
		if (us.find(str) == us.end()) {
			us.insert(str);
			vec.push_back(str);
		}
	}

	sort(vec.begin(), vec.end(), compare);

	for (string& str : vec) cout << str << '\n';

	return 0;
}

미친듯이 느리다. 해시함수를 내가 직접 구현하면 좀 더 빠를 수도.. ??