[BaekJoon 1181][⚪5] 단어 정렬
❓ 문제
🎯 난이도
Silver ⚪5
🧠 풀이
1. 내 풀이 (문자열 + 정렬)
- 알고리즘
string,Sorting
- 설명
STL의 각종 알고리즘 함수를 사용해 정렬한 풀이이다.
STL의 sort, unique를 사용해 정렬과 중복 제거를 한 번에 처리함으로써 vector 내의 원소들을 정렬하는 방식으로 해결했다. 보통은 sort로 미리 정렬을 한 상태에서 중복 제거, 그리고 다시 정렬을 하는 방식이지만, 이번 문제 같은 경우는 sort의 비교 함수로 '(문자열 길이 비교 + 문자열 비교)'를 한 번에 할 수 있어서 이렇게 하게 되었다.
참고로 가장 많이 쓰는 패턴이자 이 문제의 정석 풀이이다.
sort 함수의 시간 복잡도가 곧 이 풀이의 시간 복잡도이므로 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<string> vecWord(iN);
for(string& strInput : vecWord)
{
cin >> strInput;
}
sort(vecWord.begin(), vecWord.end(), [](const string& strPrev, const string& strNext)
{
// 길이가 같을 경우 문자열 비교
if(strPrev.length() == strNext.length())
{
return strPrev < strNext;
}
// 다르면 길이 비교
return strPrev.length() < strNext.length();
});
// 중복 제거
vecWord.erase(unique(vecWord.begin(), vecWord.end()), vecWord.end());
for(const string& strOut : vecWord)
{
cout << strOut << "\n";
}
return 0;
}
2. 추가 풀이 1 (unordered_set 풀이)
- 알고리즘
string,Sorting
- 설명
unordered_set 컨테이너를 활용한 풀이 방식이다.
삽입할 값 하나만 필요하고, '중복'을 허용치 않는 컨테이너는 set, unordered_set이 있다. 그 중에서도 unordered_set을 활용한 방식이다. unordered_set은 해싱을 사용하므로 삽입, 삭제, 탐색이 평균 O(1)로 매우 빠르므로 코테에서는 종종 set보다 자주 사용하기도 한다. 또한 위의 나의 풀이와 동시에 가장 많이 보이는 패턴의 풀이 방식이기도 하다.
unordered_set에 값을 넣을 때 해시 충돌만 일어나지 않으면, O(N log N)의 시간 복잡도를 가진다.
- 코드
내 풀이 코드
#include <iostream>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
unordered_set<string> usWord{};
vector<string> vecWord{};
usWord.reserve(iN * 2); // Rehashing 방지를 위해 넉넉하게 공간 할당
vecWord.reserve(iN);
while(iN--)
{
string strInput{};
cin >> strInput;
if(usWord.insert(strInput).second) // 삽입 성공 시 true, 실패 시 false 반환
{
vecWord.push_back(strInput);
}
}
sort(vecWord.begin(), vecWord.end(), [](const string& strPrev, const string& strNext)
{
if(strPrev.length() == strNext.length())
{
return strPrev < strNext;
}
return strPrev.length() < strNext.length();
});
for(const string& strOut : vecWord)
{
cout << strOut << "\n";
}
return 0;
}
3. 추가 풀이 2 (set 풀이)
- 알고리즘
string,Sorting
- 설명
set 컨테이너를 활용한 풀이 방식이다.
set 컨테이너의 중복 제거, 비교 정렬을 활용한 방식이다. set 컨테이너는 unordered_set이 해싱을 사용하는 것과는 대조적으로 Red-Black Tree라는 균형 이진 트리 방식으로 작동하는데, 값을 넣을 때마다 '비교 정렬'을 하므로 이에 맞게 '비교 함수 객체'를 따로 만들어주면 값을 삽입하는 동시에 '정렬'이 가능하다. 위의 두 풀이와는 다르게 컨테이너의 비교 함수 객체를 따로 만드는 방식은 문제가 조금만 더 복잡해져도 꼬이기 쉬워서 추천은 하지 않는 방식이다.
set에 N번 삽입할 때의 시간 복잡도이므로 전체적인 시간 복잡도는 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <set>
#include <string>
using namespace std;
// set에 들어갈 비교 함수 객체
struct Cmp
{
bool operator()(const string& strPrev, const string& strNext) const
{
if(strPrev.length() == strNext.length())
{
return strPrev < strNext;
}
return strPrev.length() < strNext.length();
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
set<string, Cmp> setWord{};
while(iN--)
{
string strInput{};
cin >> strInput;
setWord.insert(strInput);
}
for(const string& strOut : setWord)
{
cout << strOut << "\n";
}
return 0;
}
💭 후기
중복 제거 + 문자열 비교 정렬의 문제이고, 앞으로도 계속해서 종종 나올 알고리즘이기도 하다.
그리고 풀이는 총 세 개의 방식을 여기서 설명했고 모두 O(N log N)의 시간 복잡도를 가지지만, 막상 제출해보면
- 첫 번째 풀이 :
12ms - 두 번째 풀이 :
20ms - 세 번째 풀이 :
20ms
로 나온다.
이는 unordered_set는 해싱, 노드 할당, set은 노드 할당, 삽입마다 비교, 낮은 캐시 친화성 등의 오버헤드가 있기 때문이다. 공간 복잡도도 vector에 비해 더 크므로 사실상 내 풀이 방식이 가장 간단하면서도 범용적으로 빠르다고 볼 수 있다. 그래도 여러 풀이 방법을 알아 놓으면 나쁠 것은 없다!
Comments