[백준/C++] 알고리즘 7785번 - 회사에 있는 사람

 

안녕하세요! 테크지니어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'; 
        }
}

 

[배울 점]

- 시간복잡도를 고려해서 가장 효과적인 자료구조가 무엇인지 고민해보는 것이 중요합니다.

- 투포인터로는 어떻게 풀 수 있을지 고민해보면 좋습니다.