수많은 마라톤 선수들이 마라톤에 참여하였다.
단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.
마라톤에 참여한 선수들의 이름의 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때
완주하지 못한 선수의 이름을 return 하도록 함수를 작성하시오.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상, 100,000명 이하이다.
- completion의 길이는 participant의 길이보다 1 작다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져있다.
- 참가자 중 동명이인이 있을 수 있다.
입출력 예
| participant | completion | return |
| ["leo", "kiki", "eden"] | ["eden", "kiki"] | "leo" |
| ["marina", "josipa", "nikola","vinko","filipa"] | ["marina", "josipa", "nikola","filipa"] | "vinko" |
| ["mislav",stanko","mislav","ana"] | ["stanko","ana","mislav"] | "mislav" |
문제풀이
우리는 입력된 participant와 completion을 비교하여 가장 빠른 시간내로 데이터를 빼내고, 남는 데이터를 return하는 함수를 작성해야 한다.
가장 빠른 데이터 검색방법은 Tree방법인 Map을 사용하면 된다.
그러나, 데이터의 비교연산시 모든 텍스트를 비교해야 함으로, 헤쉬테이블을 사용하는것이 옳다.
헤시테이블의 데이터검색속도는 최소 O(1) 임[ 만약 충돌이 발생하면 O(n)이 될수도 있음] 으로 효율적이다.
participant의 모든 데이터를 헤시테이블 형태로 데이터를 정리한 뒤,
completion의 vector을 한개한개 확인하여 데이터를 지워버리고,
남는 front의 participant hashmap의 값을 도출하면 될것이다.
C++에서 지원하는 해쉬테이블인 unordered_map을 활용한다.
코드를 작성해보자.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
unordered_map<string, int> defmap;
for(auto& def : participant)
defmap[def] += 1;
for(auto& def : completion)
{
if(defmap.find(def) != defmap.end())
{
defmap[def] -= 1;
if(defmap[def] == 0) defmap.erase(def);
}
}
string answer = defmap.begin()->first;
return answer;
}코드풀이
defmap을 기준으로 작성한다.
코드의 제한상에 이름데이터가 중복되어 들어갈 수 있다고 하였음으로, 키값을 string, int형을 중첩확인용으로 넣어놓는다.
그리고, 비교해야하는 participant를 기준으로 데이터를 재정리한다.
정리한 데이터를 다시 completion을 이용하여, find로 데이터를 찾아준다. 시간복잡도는 O(1)임으로, 큰 시간이 걸리지 않는다.
같은 이름이 있을 수 있음으로, -1형태로 데이터를 빼준 다음, 0이 되었을 때, 데이터를 날려준다.
마지막으로 남은 데이터는 제한사항으로 항상 1개 남기 때문에, map의 첫번째 값 키값을 반환하면 된다.
