[백준] | C++ | 7785. 회사에 있는 사람

개요

실버2가 코앞입니다.

그래서 오늘 풀 문제는 7785. 회사에 있는 사람 입니다.

 

문제 난이도는...

실버 5입니다.

저번 글까지는 실버3 문제를 풀던 내가 어째서 실버5 문제를 풀고있어야 하는지는 잘 모르겠지만

아무생각없이 하루 1번 백준 문제 풀기를 하던 중 만만해보여서 물고온 문제가 새로운 알고리즘 분류인

'해시를 사용한 집합과 맵' 을 같이 갖고왔기 때문입니다.

 

 

 

---

 

 

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

 

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

 

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

 

문제 자체는 쉬운편입니다. 그냥 이름과 입장 여부를 둘다 받아와서 deque같은 곳에다가 enter면 때려박고 leave면 지우면 그만입니다.

 

 

---

 

 

풀이

일단 저는 알고리즘 분류따윈 보지 않고 상남자처럼 대가리부터 박아봤습니다.

 

그냥 카운트를 받아서 카운트 만큼 다시 또 인풋을 받고

그 인풋에 있는 이름을 deque에다가 넣었다가 뺐다가 하면 되겠죠.

 

저번주 목요일에 배운 반복자를 사용해볼 수 있는 좋은 실습이였습니다.

 

#include<iostream>
#include<algorithm>
#include<deque>

using namespace std;

int main()
{
    deque<string> d;

    int cnt;
    cin >> cnt;

    for (int i = 0; i < cnt; ++i)
    {
        string name, enter;
        cin >> name >> enter;

        if (enter == "enter")
        {
            d.push_back(name);
        }
        else
        {
            d.erase(find(d.begin(), d.end(), name));
        }
    }

    sort(d.begin(), d.end());

    while (d.size() != 0)
    {
        cout << *(d.end() - 1) << endl;
        d.pop_back();
    }
}

 

그냥 이런식으로 간단하게 구현했습니다.

출력은 역 사전순 이여야 한다길래 sort로 정렬 후 뒤부터 하나하나 출력했구요.

 

 

시간초과가 당연하게도 절 반겨주었고 알고리즘을 갈아 엎으려는 순간 52도 각도의 직감이 전두엽을 향해 돌진하여 그대로 제 우뇌를 관통하는 느낌의 불길함이 있었습니다.

 

정렬 알고리즘따위 집어치우고 바로 알고리즘 분류를 확인했을때 저를 또 다시 반겨준건

 

'해시를 사용한 정렬과 맵' 이였습니다.

 

우와 이게 뭐지?

저에게 해시란 그냥 Animator에서 StringToHash로 빼오는 이상한 숫자들의 연속이였는데요?
이젠 아니겠죠?

 

당장 구글링을 시작해봅시다.

찾다보니 기억난건데 사실 HashSet 같은 경우는 C#에서도 찾아볼 수 있습니다.

 

List와 유사하지만 index를 통해 접근할 수 없기 때문에 순서 정렬 따위는 상관 없는 상남자식 자료구조였습니다

당연하게도 순서와 정렬을 포기하면 속도가 따라붙겠죠? C++에서도 똑같습니다.

 

map과 set이라는 자료구조와 hash_map과 hash_set 이라는 자료구조가 있습니다.

 

이런 놈들은 연관 컨테이너라고 불리는 Key를 넣으면 Value를 주는... 그러니까
C#의 Dictionary와 비슷한 놈입니다.

 

vector나 array 같은 것들은 시퀀스 컨테이너라고 불리는데 이건 일단 킵하죠.

 

hash_map은 검색 속도가 빠른 대신 안에 있는 데이터가 적으면 오히려 오버헤드가 발생하고
데이터를 넣거나 빼는 것은 vector, list 같은 자료구조보다 느린 편입니다.

 

그렇기 때문에 몇 백 몇 천개가 넘어가는 데이터를 저장하고 잦은 수정이 없는 경우만 사용하는게 적절하다고 합니다.

근데 순서와 정렬이 없는 hash_map과 hash_set은 일단 역정렬로 출력해야하는 문제에 적합하지 않은 것 같았습니다.

 

그래서 무시까고 map으로 짜보겠습니다.

map은 값을 넣으면 자동으로 정렬해준다고 하니까 값을 다 넣은 후 거꾸로 출력하면 그만입니다.

 

Key로 이름을 넣고 Value로 입장 여부를 넣어주겠습니다.

 

#include<iostream>
#include<algorithm>
#include<deque>
#include<map>

using namespace std;

int main()
{
	map<string, string, greater<string>> m;

	int cnt;
	cin >> cnt;

	for (int i = 0; i < cnt; ++i)
	{
		string name, enter;
		cin >> name >> enter;

		m[name] = enter;
	}

	map<string, string> ::iterator it;
	for (it = m.begin(); it != m.end(); ++it)
	{
		if (it->second == "enter")
		{
			cout << it->first << '\n';
		}
	}
}

 

반복자를 검색없이 사용하려고 노력했습니다.

근데 '->' <<<<<<<< 이 놈은 배우질 못해서 검색을 할 수 밖에 없었네요.

반복자가 pair 형식이니까 첫번째값과 두번째값이 나뉘다 보니 이런식으로 접근해야 하나봅니다.

 

그리고 map에는 기본적으로 오름차 순 정렬이 들어있지만 내림차 순 정렬로 바꿀 수 있더군요.

for문을 end부터 first까지 가도록 m.end() - 1 을 해보려다가 안돼서 검색하다가 알아냈스빈다.

 

그래서 한번 제출해보면?

 

바로 정답!

 

 

 

---

 

 

마치는 말

별로 반갑지 않은 구조입니다.

머리가 아픕니다.

 

그래도 속도는 빨라서 좋습니다.