[Algorithm] 8주차 스터디 - Map과 Set 그리고 Dictionary

1. Map

1) map 이란?

• 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열이라고 생각하면 쉬움
• 각 노드가 unique한 key와 value의 쌍으로 이루어진 트리
• 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중 하나인 레드 블랙 트리로 구현되어 있음
• key를 기즌으로 정렬되어 있기 때문에 검색 속도가 빠름
• 연관 있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우에 주로 사용

 

2) c++에서 map 사용하기

• include <map>을 해야 사용 가능
• map은 중복 불가한 key와 values 쌍으로 이루어진 노드의 트리이므로 같은 key 값을 같은 노드에 추가하면 원래 노드의 values 값에 덮어씌워짐
  • ex) (2, 3)인 노드 A가 이미 존재하는 map에 (2, 4)인 노드 B를 추가하면 value는 4로 바뀌고 key는 2 하나만 존재
• map은 요소에 접근할 때, 반복자(iterator)를 이용하는 방식과 인덱스(key)를 이용하는 방식을 사용
• insert와 erase 함수의 경우 파라미터 값 자체가 아닌 iterator를 넘겨주는 방식을 사용할 수도 있음
  • ex) vector v에 있는 모든 값 추가 -> m.insert(v.being(), v.end())
  • ex) map의 첫번째 원소 삭제 -> m.erase(m.begin())

멤버 함수	기능
m.size()	m의 노드 개수를 리턴
m.empty()	m의 사이즈가 0이 아닌지를 확인
m.begin()	m의 첫번째 원소를 가리키는 iterator 리턴
m.end()	m의 마지막 원소를 가리키는 iterator 리턴
m[k] = v	m에 key가 k이고 value가 v인 노드 추가
m.insert(make_pair(k, v))
m.erase(k)	m에서 key가 k인 노드 삭제
m.find(k)	m에서 key가 k인 노드를 찾아 해당 노드를 가리키는 iterator 리턴 (key가 k인 노드가 존재하지 않을 경우, m의 마지막 원소를 가리키는 iterator 리턴)
m.count(k)	m에서 key가 k인 노드의 개수를 리턴

 

2. Set

1) set 이란?

• key만 있는 map 혹은 정렬된 집합 (key 값들이 중복을 허락하지 않으므로 정렬된 집합이라고 표현)
• map과의 차이점
  • 구조는 매우 유사하지만 가장 큰 차이점은 set은 key만 있고 value가 없는 것
• 특정 값에 대해 검색을 빠르게 하고 싶은 경우에 사용

 

2) c++에서 set 사용하기

• include <set>을 해야 사용 가능

멤버 함수	기능
s.size()	s의 노드 개수를 리턴
s.empty()	s의 사이즈가 0인지 아닌지를 확인
s.begin()	s의 첫번째 원소를 가리키는 iterator 리턴
s.end()	s의 마지막 원소를 가리키는 iterator 리턴
s.insert(k)	s에 값이 k인 노드 추가
s.erase(k)	s에서 값이 k인 노드 삭제
s.find(k)	s에서 값이 k인 노드를 찾아, 해당 노드를 가리키는 iterator 리턴 (값이 k인 노드가 존재하지 않는 경우, s의 마지막 원소를 가리키는 iterator 리턴)
s.count(k)	s에서 값이 k인 노드의 개수를 리턴

 

++) set 정렬 기준 임의로 바꾸는 방법

struct Compare {
	bool operator() (const string &a, const string &b) const{
		if (a.size() == b.size())
			return a < b;
		else
			return a.size() < b.size();
	}
};

set<int, compare> sets;

 

---

필수 문제 풀이

백준 1620 - 나는야 포켓몬 마스터 이다솜 (C++)

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

1620번: 나는야 포켓몬 마스터 이다솜

포켓몬의 이름과 번호를 도감에 입력하고, 알고 싶은 포켓몬의 이름이나 번호를 입력 받아 번호나 이름을 알려주는 문제이다.

풀이

map을 사용하여 포켓몬의 이름과 번호를 한 쌍으로 저장한다. 이때 나는 포켓몬의 이름을 key로 저장했다. 그 뒤에 알고 싶은 포켓몬의 이름이나 번호를 입력 받으면 포켓몬의 이름이 대문자로 시작한다는 것을 사용하여 이름을 입력 받았는지 번호를 입력 받았는지 확인한 후에 이름을 입력받았다면 번호를, 번호를 입력 받았다면 이름을 결과값에 넣어주면 된다.

제출한 코드

#include <iostream>
#include <vector>
#include <map>
using namespace std;

map<string, int> pokemonBook;
vector<string> pokemonName;
vector<string> result;
int pokemonNumber, question;

void input() {
    cin >> pokemonNumber >> question;

    for(int i = 1; i <= pokemonNumber; i++) {
        string name;
        cin >> name;
        pokemonName.push_back(name);
        pokemonBook.insert(make_pair(name, i));
    }
}

void findBook() {
    for (int i = 0; i < question; i++) {
        string problem;
        int problemNumber;

        cin >> problem;

        if (problem[0] >= 65 && problem[0] <= 90) {
            result.push_back(to_string(pokemonBook[problem]));
        }
        else {
            result.push_back(pokemonName[stoi(problem) - 1]);
        }
    }
}

void print() {
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << '\n';
    }
}

int main() {
    input();
    findBook();
    print();
}

 

백준 19583 - 싸이버개강총회 (C++)

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

19583번: 싸이버개강총회

개강총회에 참석자가 몇 명인지 찾아내는 문제로 참석 여부 기준은 다음과 같다. 

• 시작 시간 전이나 시작 시간에 채팅을 보냈고
• 끝난 시간부터 스트리밍이 끝나기 전에 채팅을 보낸 기록이 있다면 출석으로 인정된다.

풀이

개인적으로 이번 필수문제 중에 가장 시간이 오래걸렸던 문제이다. 이 문제는 출석을 했는지만 확인하면 되므로 map이 아닌 set을 사용해서 풀었다. 먼저 string으로 입력 받은 시간을 숫자로 바꿔서 시간을 계산해주기 위해 calculateTime 함수를 만들었다. 이를 사용하여 총회 시작시간, 총회 종료시간, 스트리밍 종료 시간을 각각 계산해 주었고, 이 값을 사용자가 채팅을 남긴 시간과 비교하여 위 기준에 맞으면 참석한 것으로, 아니라면 불참으로 처리했다. 그리고 입력 시 생길 수 있는 예외 처리도 해주었다.

제출한 코드

#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;

string startTime, endTime, quitTime;
set<string> attendance;

long long calculateTime(string time) {
	string hour = time.substr(0, 2);
	string minute = time.substr(3,2);

	return 60 * stol(hour) + stol(minute);
	
}

int main() {
	int cnt = 0;

	cin >> startTime >> endTime >> quitTime;

	long long S = calculateTime(startTime);
	long long E = calculateTime(endTime);
	long long Q = calculateTime(quitTime);


	while (cin.eof() == false) {
		string time, name;
		cin >> time >> name;

		string userHour = time.substr(0, 2);
		string userMinute = time.substr(3, 2);

		if (stoi(userHour) > 23 || stoi(userHour)<0 || stoi(userMinute) < 0 || stoi(userMinute) > 59) {
			break;
		}

		long long timeInNumber = calculateTime(time);

		if (timeInNumber <= S) {
			
			attendance.insert(name);
		}
		else if (E <= timeInNumber && timeInNumber <= Q) {
			if (attendance.find(name) != attendance.end()) {
				cnt++;
				auto it = attendance.find(name);
				attendance.erase(it);
			}
		}

	}
	cout << cnt;
}

 

백준 1764 - 듣보잡 (C++)

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

1764번: 듣보잡

듣도 못한 사람의 명단과 보도 못한 사람을 명단을 입력 받아 듣도 보도 못한 사람의 수와 명단을 출력하는 문제이다.

풀이

먼저 듣도 못한 사람의 명단을 입력 받아 map에 저장한다. 그 이후에 보도 못한 사람의 이름을 입력 받으면서 그 이름이 듣도 못한 사람의 명단이 저장되어 있는 map에 있는 이름이라면 결과값으로 출력하면 된다. 이때, 결과값을 보다 쉽게 출력하기 위해 결과값을 저장하기 위한 벡터를 하나 만들었다.

제출한 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

map<string, int> unheardOf;
vector<string> result;
int neverHeard, neverSeen;

bool neverSeenAndHeard(string personNeverSeen) {
    if (unheardOf[personNeverSeen]) {
        return true;
    }
    else {
        return false;
    }
}

void input() {
    cin >> neverHeard >> neverSeen;

    for (int i = 0; i < neverHeard; i++) {
        string personNeverHeard;
        cin >> personNeverHeard;
        unheardOf.insert(make_pair(personNeverHeard, true));
    }  
}

void checkUnheardOf() {
    for (int i = 0; i < neverSeen; i++) {
        string personNeverSeen;
        cin >> personNeverSeen;
        if (neverSeenAndHeard(personNeverSeen)) {
            result.push_back(personNeverSeen);
        }
    }
}

void print() {
    sort(result.begin(), result.end()); 
    cout << result.size() << '\n';

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << '\n';
    }
}

int main() {
    input();
    checkUnheardOf();
    print();
}

 

백준 4358 - 생태학 (C++)

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

4358번: 생태학

나무 종 이름을 입력받아 나무 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 넷째자리까지 반올림하여 출력하는 문제이다.

풀이

이 문제의 경우 입력을 받는 한도가 없기 때문에 while문 조건에 getline(cin, treeName)을 사용하여 EOF가 되면 입력이 종료되고 결과가 출력될 수 있게 했다. 그리고 cout << fixed와 cout << precision(4)를 사용하여 모든 값이 소수점 넷째자리까지 출력되도록 했다.

제출한 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

map<string, float> tree;
map<string, float>::iterator it;
int treeNumber;

void input() {
    string treeName;
    
    while (getline(cin, treeName)) {
        tree[treeName]++;
        treeNumber++;
    }
}

void print() {
    cout << fixed;
    cout.precision(4);

    for (it = tree.begin(); it != tree.end(); it++) {
        cout << it->first << ' ' << it->second * 100 / (double)treeNumber  << '\n';
    }
}

int main() {
    input();
    print();
}

 

Reference

• https://sarah950716.tistory.com/6
• https://chanhuiseok.github.io/posts/algo-46/