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;
}
미친듯이 느리다. 해시함수를 내가 직접 구현하면 좀 더 빠를 수도.. ??
'BOJ_단계별로 풀어보기(9단계~) > [11단계] 정렬' 카테고리의 다른 글
| [백준 18870] 좌표 압축 (0) | 2022.03.10 |
|---|---|
| [백준 10814] 나이순 정렬 (0) | 2022.03.09 |
| [백준 11651] 좌표 정렬하기 2 (0) | 2022.03.09 |
| [백준 11650] 좌표 정렬하기 (0) | 2022.03.09 |
| [백준 1427] 소트인사이드 (0) | 2022.03.08 |
