문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다.
내 접근
- 정렬 조건이 문자열 길이 우선, 그 다음 사전 순이니까, 내가 직접 비교 함수를 만들어도 되겠지만
std::pair의 기본 비교 동작에 위임할 수도 있겠다. - 중복되는 문자열은 제거해야하네? Set으로 중복을 먼저 제거하고 정렬할 데이터를 구성하는게 낫겠다.
구현
#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#include <algorithm>
#include <set>
#include <vector>
void solve() {
int n;
std::cin >> n;
std::set<std::string> s;
std::string x;
for (int i = 0; i < n; i++) {
std::cin >> x;
s.insert(x);
}
std::vector<std::pair<int, std::string>> v;
v.reserve(s.size());
std::transform(
s.begin(), s.end(), std::back_inserter(v),
[](const std::string &s) { return std::make_pair(s.length(), s); });
std::sort(v.begin(), v.end());
for (const auto &p : v) {
std::cout << p.second << '\n';
}
}
int main() {
IO;
solve();
return 0;
}
개선점
Set이 필요했는가?
- Set 은 사전 순으로 정렬됨
- 삽입에 O(log n) 걸림
- 정렬 기준이 문제와 다름(문제는 길이 + 사전순)
- 중복 제거 용도로만 사용하는게 맞는가?
std::unique와 std::erase를 이용해서 중복을 제거하는 방법도 있었다.
std::vector<std::string> v(n);
std::sort(v.begin(), v.end(),
[](const std::string& a, const std::string& b) {
return (a.length() < b.length()) || (a.length() == b.length() && a < b);
}
);
v.erase(std::unique(v.begin(), v.end()), v.end());std::unique 연속되는 중복 요소를 삭제한다(대상이 정렬되어있다는 전제가 있다).
하지만 대상이 되는 컨테이너의 길이 등을 변경하진 않기 때문에 쓰레기 값이 남는다.
std::unique는 쓰레기 값 앞의 포인터를 반환하므로, 어디부터 지워야하는지 알 수 있다.
vector::erase를 사용할 때는 std::unique 반환 값부터 vector::end 까지 지우면 되겠다.