[Programmers] 완주하지 못한 선수

문제 

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

• completion의 길이는 participant의 길이보다 1 작습니다.

• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

• 참가자 중에는 동명이인이 있을 수 있습니다.

👉 programmers.co.kr/learn/courses/30/lessons/42576?language=cpp

문제요약

총 n명의 선수들이 마라톤 경기에 참여하여 n-1명의 선수들이 마라톤을 완주하였을 때 완주하지 못한 1명이 누구인지 구하는 문제입니다. 여기서 정말 많이 헤맸던 점은 동명이인이 있을 수도 있다!라는 점입니다. 

첫번째 풀이 (통과 x)

이 문제를 보고 아무 생각없이 가장 간단한 방법으로 아래와 같이 풀었습니다. 아래의 풀이는 다음과 같아요.

1. 완료한 선수들을 한명씩 참가자 전원과 비교하며 이름이 일치할경우 제거

2. 남은 선수가 완주하지 못한 1인

#include <string>
#include <vector>

using namespace std;

string solution1(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    for (int i = 0; i < completion.size(); i++) {
        for (int j = 0; j < participant.size(); j++) {
            if (completion[i] == participant[j]) {
                participant.erase(participant.begin() + j);
                break;
            }
        }
    }
    
    answer = participant[0];
    return answer;
}

이렇게 풀었더니 효율성에서 0점을 받았습니다. 

제한사항에 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하라고 하니 위 코드의 시간 복잡도는 O(n^2)이므로 1초를 넘기게 되는데 이 문제는 이 시간보다 더 빠르게 풀어야 되는 것 같습니다.

두번째 풀이 (통과 x)

그렇다면 O(n^2)보다 줄이는 방법을 생각해보았습니다. 마라톤 선수들의 이름을 key값으로 해시테이블을 구성한다면 위와 같이 이중포문을 이용해서 접근하지 않아도 될 것 같아요:) STL라이브러리 중 하나인 map을 사용하여 <string, bool> map을 만들어, 완주를 하지 못 했다면 false, 완주했다면 true 로 구분해볼 수 있어요.

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    map<string,bool> m;
    
    for (int i = 0; i < participant.size(); i++) {
        m.insert(make_pair(participant[i], false));
    }
    
    for (int i = 0; i < completion.size(); i++) {
        m[completion[i]] = true;
    }
    
    for (map<string,bool>::iterator it = m.begin(); it != m.end(); it++) {
        if (it->second == false) {
            answer = it->first;
            break;
        }
    }
    
    return answer;
}

이렇게 풀었더니 이번엔 제한사항인 동명이인의 테스트케이스를 통과하지 못합니다. 

세번째 풀이 (통과 o)

동명이인까지 고려해야 한다면 value값을 bool타입이 아닌 int타입으로 바꾸고 이름의 개수로 넣어주어서 해결할 수 있을 것 같아요. map에서 find를 이용하였는데 key값이 없다면 map.end()를 return해주고 key값이 있다면 value값을 return해주는 메소드입니다.

아래는 해결한 코드입니다!

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

using namespace std;

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

 

알고리즘을 생각해보면 다음과 같이 정말 간단해요.

1. 참여한 마라톤 선수들의 이름들을 자료구조에 저장한다.

2. 완료한 마라톤 선수들의 이름을 제거한다.

이렇게 되면 남은 마라톤 선수가 완주하지 못한 선수가 되니까요. 하지만 이 문제에서 중요했던 점은 어떤 자료구조를 사용해야 할까인 것 같아요. 해시테이블을 사용하면 빠르게 탐색이 가능하여 효율성도 증가하는 것을 알 수 있었습니다.

재밌는 풀이

해시를 이용해서만 풀 수 있을까 고민하다가 다르게도 풀리더라고요!!! vector배열을 정렬하면 이름순서가 동일하게 정렬되어 하나씩 비교해볼 수 있습니다. 아래와 같은 풀이도 적어보았습니다. 배열의 수가 1개 차이가 나서 이렇게도 풀 수 있었던 것 같아요. 통과하고 나서 보니까 사람들 대부분 아래의 방식대로 풀었더라고요 😿

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

using namespace std;

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