[C++] 백준 7785번 map

알고리즘

목록 보기

7/20

백준 7785. 회사에 있는 사람

N개의 출퇴근 기록을 보고, 회사에 남아있는 사람의 이름을 안사전순으로 출력하는 문제이다.
엊그제 배운 pair 객체를 써서 풀어보려 했는데 어떻게 해도 지저분해서 새로운 걸 또 배웠다.
세상엔 내가 모르는 것이 왜이리 많은지
그것은 아직 공부하기 전이기 때문.

map

map은 key - value를 쌍으로 갖는 정렬된 컨테이너이다.
default는 오름차순 정렬이며 중복을 허용하지 않는다.
검색, 삭제, 삽입 연산의 시간복잡도는 O(log n)이고, 레드-블랙 트리 기반으로 구현되어 있다.

레드-블랙 트리
이진 탐색 트리의 일종으로, 구현하기 복잡하지만 일정한 규칙을 갖고 있어 최악의 경우에도 O(log n)의 복잡도를 유지한다.

map 선언

#include <map>

// map <key type, value type, cmp> name;
// 문제에서 이름과 출퇴근 기록("enter", "leave")이 string type
// 출력 조건이 사전의 역순이므로 greater<> 또는 greater<string> 사용
map<string, string, greater<>> m;

map 접근

1. 인덱스 기반 (1)

for (auto it = m.begin(); it != m.end(); it++) {
	cout << it->first << " " << it->second << endl;
}

2. 인덱스 기반 (2)

map<string, string>::iterator it;

for (it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << "\n";
}

3. 범위 기반

for (auto it : m) {
	cout << it.first << " " << it.second << "\n";
}

나중에 auto랑 iterator 하고 -> 요것들도 알아봐야지.

풀이

n, name, act 를 입력 받아 map에 넣어준다.
요 때 map은 중복을 참지 않으므로 같은 이름(key)에 다른 출퇴근 기록이 들어오면 자동으로 value 값만 바뀌는 걸 확인할 수 있다.

이 좋은 넘을 이제 알았다니 ~

입력 후 바로 출력하면 끝인데
second 값. 그러니까 해당 key(name)의 마지막 value(act) 값이 enter인 사람의 이름만 출력해주면 된다.

코드

#include <iostream>
#include <map>
#include <string>

using namespace std;

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

	int n;
	cin >> n;

	map<string, string, greater<>> m;
	string name, act;
	for (int i = 0; i < n; i++) {
		cin >> name >> act;
		m[name] = act;
	}

	for (auto it : m) { // <-- 범위 기반이 마음에 들엇스. (간따내)
		if (it.second == "enter") cout << it.first << "\n";
	}

	return 0;
}