💻 완주하지 못한 선수

분류 : Hash (해시)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

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

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

제한 사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

해결 방안

한 명의 선수를 제외하고 모든 선수가 마라톤을 완주했다.

참가한 선수들의 배열과 완주한 선수들의 배열이 주어질 때, 완주 못한 선수의 이름을 return 해라.

방법은 여러 가지가 있을 것이다.

각각 하나씩 붙들고 이중 for 문으로 여러 번 돌려봐도 되고,

단 한 개를 찾는 것이기 때문에 정렬 후에 각각 비교해봐도 되고

STL의 Set을 통하여 Find를 사용해도 될 것으로 보인다.

💡 문제 풀이

방법 1 )

모든 경로를 돌며 같은 이름이 있을 시, 제거하고 다음으로 넘어가 마지막 남은 변수를 return 한다.

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    
    for (vector<string>::iterator iter = completion.begin(); iter != completion.end(); iter++) {
        // participant의 맨 뒤를 기준으로 completion을 돌면서 찾는다.
        if (participant.back() == *iter) {	
            // 만약 동일한 값을 찾을 시, 두 vector에서 제거해주고 
            // iterator를 다시 맨 앞으로 돌려준다.
            participant.pop_back();
            completion.erase(iter);
            iter = completion.begin() - 1;
            continue;
        }
        
        // 만약 찾지 못하고 모든 루프를 돌았다면 for문은 탈출하게 된다.
    }

    return participant.back();
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.91MB)
    테스트 2 〉	통과 (0.01ms, 3.96MB)
    테스트 3 〉	통과 (0.42ms, 3.97MB)
    테스트 4 〉	통과 (1.08ms, 3.95MB)
    테스트 5 〉	통과 (1.39ms, 3.82MB)

효율성  테스트
    테스트 1 〉	실패 (시간 초과)
    테스트 2 〉	실패 (시간 초과)
    테스트 3 〉	실패 (시간 초과)
    테스트 4 〉	실패 (시간 초과)
    테스트 5 〉	실패 (시간 초과)

채점 결과
    정확성: 50.0
    효율성: 0.0
    합계: 50.0 / 100.0
*/

시간 복잡도 : n^2 - n

정확성 테스트는 통과하였으나 효율성 테스트에서 실패하였다.
시간 복잡도가 너무 비싼 것이 문제였다.

방법 2 )

두 vector를 정렬한 후에 맨 앞에서부터 대조해본다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    // STL Algorithm의 Sort를 사용 
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < participant.size()-1; i++) {
        // for문을 통하여 순차적으로 비교, 만약 동일하지 않을 시 participant의 값이 정답
        if (participant[i] != completion[i]) return participant[i];
    }

    // 맨 마지막까지 동일할 시 맨 뒤에 있는 값 return
    return participant.back();
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.94MB)
    테스트 2 〉	통과 (0.01ms, 3.95MB)
    테스트 3 〉	통과 (0.31ms, 3.89MB)
    테스트 4 〉	통과 (0.59ms, 3.94MB)
    테스트 5 〉	통과 (0.59ms, 3.91MB)

효율성  테스트
    테스트 1 〉	통과 (37.02ms, 14.4MB)
    테스트 2 〉	통과 (57.74ms, 19.7MB)
    테스트 3 〉	통과 (71.33ms, 23.3MB)
    테스트 4 〉	통과 (79.01ms, 25.4MB)
    테스트 5 〉	통과 (78.32ms, 25.4MB)

채점 결과
    정확성: 50.0
    효율성: 50.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n * log n + n

둘 다 똑같은 방식으로 정렬을 한 뒤 맨 앞에서부터 대조해 보았을 때, 같은 값은 같은 위치에 있을 것이다.

하나 한 가지 빠진 이름으로 인하여 다른 값이 있다면 그 값은 participant에는 있지만 completion에는 없을 것이다.

방법 3 )

Unordered Multiset 을 사용하여 컨테이너의 Find 를 사용한다.

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    // 완주자 목록을 담은 unordered_multiset
    // 동명이인이 있을 수 있어 multiset을 사용
    // 문제 속 정렬이 필요 없어 unordered 사용
    unordered_multiset <string> completion_set(completion.begin(), completion.end());

    for (int i = 0; i < participant.size(); i++) {
        // find를 통하여 iterator를 저장, 못 찾을 시 completion_set.end()가 저장됨.
        unordered_multiset<string>::iterator iter = completion_set.find(participant[i]);

        // completion_set.end()일 시 정답, 아닐 시 제거
        if (iter == completion_set.end()) return participant[i];
        else completion_set.erase(iter);
    }
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.02ms, 3.93MB)
    테스트 2 〉	통과 (0.01ms, 3.87MB)
    테스트 3 〉	통과 (0.14ms, 3.98MB)
    테스트 4 〉	통과 (0.33ms, 3.97MB)
    테스트 5 〉	통과 (0.26ms, 3.96MB)

효율성  테스트
    테스트 1 〉	통과 (14.15ms, 18.2MB)
    테스트 2 〉	통과 (28.51ms, 25.3MB)
    테스트 3 〉	통과 (28.51ms, 30.3MB)
    테스트 4 〉	통과 (29.32ms, 32.7MB)
    테스트 5 〉	통과 (45.89ms, 32.9MB)

채점 결과
    정확성: 50.0
    효율성: 50.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : n * log n

set의 find는 log n 정도의 시간 복잡도를 갖고 있어 많은 양의 데이터에서 무엇을 찾는데 용이하다.

unordered_multiset을 이용한 이유는 문제 속에 동명이인이 있을 수 있어 multiset을 사용하고, 자체적으로 정렬을 하지 않기 때문에 multiset보다 빠르다.