안녕하세요! 테크지니어22입니다.
오늘은 백준 알고리즘 7785번 회사에 있는 사람 문제를 풀어보도록 하겠습니다.
https://www.acmicpc.net/problem/7785
[문제 접근]
- 각 사람마다 최종적인 값이 enter인지 파악이 관건이라고 생각했습니다. 또한 enter의 개수가 leave개수보다 많아도 동일하다고 생각했습니다.
- 시간 제한은 1초이고, n이 백만입니다. 1억번 연산하는데 c++은 대략 1초가 걸리니 시간복잡도가 N^2 풀이는 이 문제를 통과할 수 없습니다. 해시, 이진 검색 트리, 이분 탐색, 투포인터가 떠올랐습니다.
[풀이 전략]
- unordered_map과 map 중 고민하다가 최종 출력이 이름 역순이어서 이미 순서가 정해진 ordered_map이 더 간단하다고 판단이 들어서 map을 이용하였습니다.
- 첫번째 풀이는 ordered_map을 이용하여 풀이를 하였지만 set을 이용한 풀이, unordered_set을 이용한 풀이, 이분탐색을 이용한 풀이를 진행하였습니다.
[코드]
map 풀이 -> O(NlogN)
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
int n ;
cin >> n ;
map<string,int> m ;
for(int i = 0 ; i < n ; i++) {
string k, v ;
cin >> k >> v ;
if(v == "enter") m[k] = 1;
else m[k] = 0 ;
}
for (auto it = m.rbegin(); it != m.rend(); ++it) {
if(it->second) cout << it->first << '\n';
}
}
Set 풀이 -> O(NlongN)
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
int n ;
cin >> n ;
set<string> s ;
for(int i = 0 ; i < n ; i++) {
string k, v ;
cin >> k >> v ;
if(v == "enter") s.insert(k);
else s.erase(k);
}
for (auto it = s.rbegin(); it != s.rend(); ++it) {
cout << *it << '\n';
}
}
unodered_set 풀이 → O(nlogn)
- 해시 시간복잡도는 O(1)이나 정렬이 O(nlogN)
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
int n ;
cin >> n ;
unordered_set<string> s ;
for(int i = 0 ; i < n ; i++) {
string k, v ;
cin >> k >> v ;
if(v == "enter") s.insert(k);
else s.erase(k);
}
vector<string> ans(s.begin(),s.end());
sort(ans.begin(),ans.end(),greater<string>() );
for(auto e: ans) cout << e <<'\n';
}
이분탐색 풀이 O(nlogn)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
int n ;
cin >> n ;
vector<string> e, l,ans ;
for(int i = 0 ; i < n ; i++) {
string k,v ;
cin >> k >> v ;
if( v == "enter" ) e.push_back(k);
else l.push_back(k);
}
sort(e.begin(), e.end());
sort(l.begin(), l.end());
auto it = e.begin();
while(it != e.end()){
int ecnt =(upper_bound(e.begin(), e.end(), *it) - lower_bound(e.begin(), e.end(), *it));
int lcnt =(upper_bound(l.begin(), l.end(), *it)- lower_bound(l.begin(), l.end(), *it));
if(ecnt > lcnt) {
ans.push_back(*it);
}
it = upper_bound(e.begin(), e.end(), *it) ;
}
sort(ans.begin(),ans.end(),greater<string>());
for(auto ele : ans) {
cout << ele << '\n';
}
}
[배울 점]
- 시간복잡도를 고려해서 가장 효과적인 자료구조가 무엇인지 고민해보는 것이 중요합니다.
- 투포인터로는 어떻게 풀 수 있을지 고민해보면 좋습니다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준/C++] 알고리즘 1806번 - 부분 합 (0) | 2024.09.28 |
---|---|
[백준/C++] 알고리즘 1620번 - 나는야 포켓몬 마스터 이다솜 (3) | 2024.09.28 |
[백준/C++] 알고리즘 22862번 - 가장 긴 짝수 연속한 부분 수열 (1) | 2024.05.15 |
[알고리즘/C++] 에라토스테네스의 체 (0) | 2024.05.13 |
[백준/C++] 알고리즘 1744번 - 수 묶기 (0) | 2024.05.03 |