백준 s5 7785 회사에 있는 사람 c++ 이분탐색, 해시

https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

문제

N개의 "사람이름 enter/leave"로 구성된 출입기록이 주어진다. enter인 경우엔 출근, leave인 경우엔 퇴근이다. 현재 회사에 남아있는 사람들의 이름을 사전역순으로 출력하기

 

풀이

이 문제는 이분탐색과 해시(unordered_set)으로 풀 수 있다.

 

풀이1. 이분탐색 

enter의 개수와 leave의 개수를 이분탐색의 upper_bound - lower_bound로 구할 수 있다. 

enter 목록 / leave 목록 만들기
목록 정렬
unique한 enter 목록 만들기

for unique한 enter목록 // O(N)
	enter 개수, leave 개수 count // O(logN)
    if enter 개수 > leave 개수
    	answer.push_back(이름)

 

전체 코드

/*boj s5 7785 회사에 있는 사람_ binary search*/
#include <algorithm>
#include <iostream>
#include <vector>
#define MAXN 1000005
using namespace std;

int N;
vector<string> enter;
vector<string> leave;

vector<string> uEnter;
vector<string> answer;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        string name, inout;

        cin >> name >> inout;

        if (inout[0] == 'e') {
            enter.push_back(name);
        } else {
            leave.push_back(name);
        }
    }
    sort(enter.begin(), enter.end());
    sort(leave.begin(), leave.end());

    uEnter = enter;
    uEnter.erase(unique(uEnter.begin(), uEnter.end()), uEnter.end());

    for (string n : uEnter) {
        int eCnt = upper_bound(enter.begin(), enter.end(), n) - lower_bound(enter.begin(), enter.end(), n);
        int lCnt = upper_bound(leave.begin(), leave.end(), n) - lower_bound(leave.begin(), leave.end(), n);
        if (eCnt > lCnt) {
            answer.push_back(n);
        }
    }

    sort(answer.begin(), answer.end(), greater<>());

    for (string n : answer) {
        cout << n << "\n";
    }
}

 

풀이2. 해시

unordered_set으로 만약 해당 이름이 없으면 추가, (enter) 이미 있으면 삭제(퇴근)하면 된다.

 

+) unordered_set은 sort로 정렬이 불가하다. 왜냐하면 내부적으로 순서가 뒤섞인 채로 해시테이블에 저장되어있기 때문이다.

따라서 vector로 바꿔준 후에야 sort가 가능

vector<string> vec (hash.begin(), hash.end());

 

전체 코드

/*boj s5 7785 회사에 있는 사람_ hash*/
#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>
#define MAXN 105
using namespace std;

int N;
unordered_set<string> S;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        string name, inout;
        cin >> name >> inout;

        if (S.find(name) == S.end()) {
            S.insert(name);
        } else { // 이미 이름이 있으면
            S.erase(name);
        }
    }
    vector<string> sortedS(S.begin(), S.end());
    sort(sortedS.begin(), sortedS.end(), greater<>());

    for (string n : sortedS) {
        cout << n << "\n";
    }
}