[BaekJoon 1764][⚪4] 듣보잡
❓ 문제
🎯 난이도
Silver ⚪4
🧠 풀이
1. 내 풀이 (정렬 + 해시 셋)
- 알고리즘
Data Structure,Sorting,Set & Map,Hashing
- 설명
unordered_set과 정렬을 사용하는 풀이이다.
입력값은 중복이 없고, 정렬이 필요 없는 상태이고 그 상태에서 원하는 결과값을 찾는게 목적인 문제이다 보니 unordered_set이 생각 났고, vector와 sort를 같이 사용해서 푼 방식이다.
unordered_set에서 값을 찾기 위해 count를 썼고, 찾은 값은 결과 vector에 다시 저장한 다음 마지막에 sort 한 뒤 출력했다. 추가적으로 string을 사용한 출력 최적화도 시도해 봤는데 별 효과는 없었다.
unordered_set의 삽입, 탐색의 시간은 O(1)이고 sort는 O(N log N)이라서 전체적인 시간 복잡도는 sort를 따라가 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{}, iM{};
cin >> iN >> iM;
unordered_set<string> usetName{};
usetName.max_load_factor(0.7f); // 해시 충돌 방지용 load factor 조절
usetName.reserve(iN * 2); // 넉넉한 공간 할당
while(iN--)
{
string strNHeard{};
cin >> strNHeard;
usetName.emplace(strNHeard);
}
vector<string> vecName{};
vecName.reserve(iM);
while(iM--)
{
string strNSeen{};
cin >> strNSeen;
// 이미 unordered_set에 값이 있는지 확인
if(usetName.count(strNSeen))
{
vecName.push_back(strNSeen);
}
}
sort(vecName.begin(), vecName.end());
cout << vecName.size() << '\n';
// 출력 최적화용 코드
string strOut{};
strOut.reserve(1 << 20);
for(const string& strName : vecName)
{
strOut += (strName + '\n');
if(strOut.size() >= (1 << 19))
{
cout << strOut;
strOut.clear();
}
}
cout << strOut;
return 0;
}
2. 추가 풀이 1 (정렬 + 투 포인터)
- 알고리즘
Data Structure,Sorting,Two Pointer
- 설명
투 포인터 알고리즘과 정렬을 사용하는 풀이이다.
vector 컨테이너 두 개에 입력값들을 모두 저장하고, sort를 통해 정렬한다. 그 다음 결과값을 찾는 과정에서 두 개의 정수형 '포인터' 변수로 반복문을 돌며 같은 값을 찾아내는 방식이다.
일단 컨테이너가 vector로 통일이 되어 있고, 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{}, iM{};
cin >> iN >> iM;
vector<string> vecNHeard(iN);
vector<string> vecNSeen(iM);
for(string& strNHeard : vecNHeard)
{
cin >> strNHeard;
}
for(string& strNSeen : vecNSeen)
{
cin >> strNSeen;
}
// 미리 정렬
sort(vecNHeard.begin(), vecNHeard.end());
sort(vecNSeen.begin(), vecNSeen.end());
vector<string> vecResult{};
vecResult.reserve(iM);
int iNHeard{}, iNSeen{};
// 각각의 포인터가 끝까지 갈 때까지 반복
while(iNHeard < iN && iNSeen < iM)
{
string strNHeard{ vecNHeard[iNHeard] };
string strNSeen{ vecNSeen[iNSeen] };
// 같은걸 찾으면 결과 벡터에 push, 포인터 둘 다 이동
if(strNHeard == strNSeen)
{
vecResult.push_back(strNHeard);
++iNHeard;
++iNSeen;
}
// 같은걸 못찾으면 각각의 포인터 따로 이동
else if(strNHeard < strNSeen)
{
++iNHeard;
}
else
{
++iNSeen;
}
}
cout << vecResult.size() << '\n';
for(const string& strResult : vecResult)
{
cout << strResult << '\n';
}
return 0;
}
3. 추가 풀이 2 (정렬 + 이분 탐색)
- 알고리즘
Data Structure,Sorting,Binary Search
- 설명
이분 탐색 알고리즘을 사용하는 풀이이다.
vector 컨테이너에 입력값들을 모두 넣고 sort를 통해 정렬을 해준 뒤, binary_search 함수를 통해 이분 탐색으로 원하는 결과값을 뽑아내는 방식이다.
사실 원하는 값을 찾아내는게 가장 중요한 이 문제에서 binary_search 함수 하나로 값을 찾아낼 수 있으니 로직 자체가 굉장히 심플해진다. 컨테이너도 입력과 결과만을 담을 두 개만 필요해서 위의 두 풀이보다 메모리 할당도 적다.
sort의 시간 복잡도는 O(N log N), binary_search의 시간 복잡도는 O(log N)이므로 전체 시간 복잡도는 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{}, iM{};
cin >> iN >> iM;
vector<string> vecNHeard(iN);
for(string& strNHeard : vecNHeard)
{
cin >> strNHeard;
}
// 이분 탐색 전에 정렬 필수
sort(vecNHeard.begin(), vecNHeard.end());
vector<string> vecResult{};
vecResult.reserve(iM);
while(iM--)
{
string strNSeen{};
cin >> strNSeen;
// 값이 있는지 이분 탐색, 찾으면 결과 벡터에 push
if(binary_search(vecNHeard.begin(), vecNHeard.end(), strNSeen))
{
vecResult.push_back(strNSeen);
}
}
// 결과값은 정렬이 안된 상태이므로 다시 정렬
sort(vecResult.begin(), vecResult.end());
cout << vecResult.size() << '\n';
for(const string& strResult : vecResult)
{
cout << strResult << '\n';
}
return 0;
}
💭 후기
사실 이 문제에서 바라는 풀이법은 알고리즘 분류로 봤을 때는 첫번째 풀이인 것 같다. 실제로 세 풀이간의 실행 시간의 차이는 최대 4ms로 무의미한 수준의 차이긴 하지만, unordered_set의 reserve를 크게 잡을 때 가장 빠른건 첫 번째 풀이기도 하다.
하지만 '해시 충돌'의 가능성, '메모리 공간', 로직의 '가독성'을 생각해보면 개인적으로 마음에 드는건 세 번째 풀이이다.
Comments