[Baekjoon] 7785번: 회사에 있는 사람

 

 

 

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

7785번: 회사에 있는 사람

 

---

 

문제 해결 과정

착안

많은 문자열에 대해, 입출력마다 요소를 보관할 컨테이너에 요소가 존재하는지 판단해야하기 때문에 해시(hash) 코드를 키로 가지는 std::map<> 클래스를 이용하고자 했다. 이때 주어지는 문자열의 길이가 5 이하이므로 매우 짧은 편에 속해, unsigned long long 자료형과 다항 롤링 해시(polynomial rolling hash)를 사용하면 간단하게 해시 코드를 계산할 수 있으면서 충돌 없이 1대 1로 매칭시킬 수 있으므로 이와 같은 방법을 사용하고자 하였다.

 

구현

std::map<> 클래스는 기본적으로 키의 값으로 요소들을 정렬하면서 삽입/제거하므로 키 값을 정렬할 이항 조건을 별도로 람다 표현식(lambda expression)을 사용해 제공해주었다. 한편, 문자열 "leave" 가 들어왔을 때 요소를 지우는 것보다 표시만 해둔 다음 최종 출력 시 이를 확인하여 출력하는 것이 시간 복잡도 상으로 더 유리할 것으로 생각하여 이와 같이 구현하였다.

 

std::map<> 클래스를 사용함에 있어서 한 가지 배운 점은 [] 연산자를 사용하여 요소를 삽입/수정하는 메커니즘인데, 요소가 존재할 경우에는 값을 갱신하고 존재하지 않을 때에는 요소를 새로 추가하는 메커니즘을 가지므로 이를 이용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <map>

using namespace std;

size_t P[5] = { 12117361, 205379, 3481, 59, 1 };

struct Worker
{
	char Name[6];
	bool Entered;
};

size_t HashFunction(char str[6])
{
	size_t hash = 0;
	for (int i = 0; i < 5; i++)
		if (str[i])
			hash += P[i] * (str[i] - 'A' + 1);

	return hash;
}

map<size_t, Worker, std::greater<>> Workers;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	while (N--)
	{
		Worker worker;
		char op[6] = { 0, };

		cin >> worker.Name >> op;
		worker.Entered = op[0] == 'e';
		Workers[HashFunction(worker.Name)] = worker;
	}

	for (auto elem : Workers)
		if (elem.second.Entered)
			cout << elem.second.Name << "\n";

	return 0;
}

 

실행 결과