프로그래머스: 완주하지 못한 선수 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42576

알고리즘 연습 - 완주하지 못한 선수 | 프로그래머스

 

해쉬 카테고리에 있어서 무조건 그렇게 풀려고 시도했다.

 

결론적으로 multimap을 이용해서, 선수들의 이름을 map의 key에 넣고,

 

value는 이 문제에선 큰 의미가 없기 때문에 그냥 순서로 정해주었다.

 

이후, 완주 한 사람을 찾아서 원래의 map에서 지워주면 자연스럽게 남는 사람이 완주하지 못한 사람이 된다.

 

#include<iostream>
#include<map>
#include<string>
#include<vector>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
	string answer = "";

	multimap<string, int> mm;
	for (int i = 1; i <= participant.size(); i++) {
		mm.insert({ participant[i - 1], i });
	}
	for (int i = 0; i < completion.size(); i++) {
		mm.erase(mm.lower_bound(completion[i]));
	}
	return mm.begin()->first;
}

 

STL의 사용이 익숙하지 않았기 때문에, 사전에 공부가 필요했다.

 

동명이인이 있을 수 있다고 문제 조건에 명시되어 있으므로 map이 아닌 multimap을 사용했다.

 

pair를 다룬다고 생각하고 {key, value} 꼴로 map에 insert 해주면 된다.

 

lower_bound는 같은 key를 가진 데이터들 중에서, 가장 첫번째의 원소를 의미하는 것이다.

 

upper_bound를 이 문제에서 사용하지는 않았지만, upper_bound를 사용하면, 가장 마지막 원소가 아니라,

 

가장 마지막 원소보다 한 칸 더 이후를 의미하는 것 같았다.

 

자료구조에 대해 곧 자세히 정리해야겠다.