[프로그래머스] 완주하지 못한 선수

문제

1명의 선수를 제외하고, 모두 완주

참여 선수들 이름 : participant
완주 선수들 이름 : completion

제한사항
총 선수는 1명 이상 10만명 이하
각 이름은 1개 이상 20개 이하의 알파벳 소문자
동명이인 가능

@ 완주 못한 선수 이름

 

[아이디어]

집합으로 따지면 A⊃B에서  A-B을 떠올렸으나, 동명이인이 가능하다고 하여 집합 생각은 x

해시 카테고리여서인지 map으로 각 이름을 key로, 해당 이름을 가진 사람 수를 value로 해도 되겠다 생각

 

[구현]

#include <string>
#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    map<string, int> p;
    
    for (int i = 0; i < participant.size(); i++) {
            p[participant[i]]++;
    }
    for (int i = 0; i < completion.size(); i++) {
        string name = completion[i];
        if (p[name] > 1)
            p[name]--;
        else
            p.erase(name);
    }
    
    answer = p.begin() -> first;
    return answer;
}

 

 

맵에서 value로 들어가는 값이 다 다른 게 아니라 1인 경우가 많은데 굳이 map을 써야할까 싶어서

vector만을 이용하여 다른 방법으로 구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    for (int i = 0; i < participant.size() - 1; i++) {
        if (participant[i] != completion[i])
            return participant[i];
    }
    
    return participant[participant.size()-1];
}

 

주의할 점

for 반복문에서 i 인덱스가 마지막 인덱스까지 가버리면, completion 벡터는 participant보다 크기가 하나 작으므로 오버플로우가 발생한다.

-> 마지막 인덱스 전까지만 비교 & return 없이 반복문이 통과되면 participant의 마지막 값 return