<프로그래머스> Level1 완주하지 못하는 선수

완주하지 못하는 선수

문제

문제 설명

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

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

제한사항

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

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

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

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

출처:https://programmers.co.kr/learn/courses/30/lessons/42576

문제 풀이

뭔가 첫번째 풀이는 효율성 테스트를 통과 하지 못할 것 같았는데 역시나였다. 첫번째 풀이의 방법은 vector와 algorithm STL을 이용하여 풀었다.

1. completion에서 원소 하나를 선택하여 find() 함수를 사용하여 particpant에서의 위치를 찾는다.

2. 만약 존재한다면 particpant에서 그 원소를 삭제한다.

3. 이과정을 반복하여 completion의 끝까지 도달했다면 participant에 마지막 원소를 반환하고 중간에 find()로 찾지 못했다면 그값을 반환한다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    vector<string>::iterator iter;
    int i =0;
    while(completion.size()!=i){
        iter = find(participant.begin(),participant.end(),completion[i]);
        if(iter == participant.end()){
            return completion[i];
        }else{
            participant.erase(iter);
        }      
        i++;
    }
    return participant[0];
}

결과는... 효율성 테스트를 하나도 통과 하지 못하였다. 생각해보니 while()문과 erase로 인하여 시간복잡도가 O(n*n)이 되서 효율성 테스트에서 실패하는것 같다.

 

채점을 시작합니다.
정확성  테스트
테스트 1 〉
통과 (0.01ms, 3.72MB)
테스트 2 〉
통과 (0.01ms, 3.79MB)
테스트 3 〉
통과 (0.44ms, 3.95MB)
테스트 4 〉
통과 (1.61ms, 3.88MB)
테스트 5 〉
통과 (1.78ms, 3.86MB)
효율성  테스트
테스트 1 〉
실패 (시간 초과)
테스트 2 〉
실패 (시간 초과)
테스트 3 〉
실패 (시간 초과)
테스트 4 〉
실패 (시간 초과)
테스트 5 〉
실패 (시간 초과)
채점 결과
정확성: 50.0
효율성: 0.0
합계: 50.0 / 100.0

고민하다가 다시 인터넷을 찾아보았다. 구글링을 그만해야 하는데..ㅎ

정렬을 이용한 풀이는 다음과 같다 :

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(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];
        }
    }
    
    return participant.back();
}

두개의 배열은 하나의 원소가 더 많고 그 외에는 모두 같은 원소이므로 sort()를 이용하여 정렬한 후 앞에서부터 하나씩 비교하면 된다.. 이러면 시간 복잡도가 O(n)이 나온다. 

정확성  테스트
테스트 1 〉
통과 (0.01ms, 3.85MB)
테스트 2 〉
통과 (0.01ms, 3.8MB)
테스트 3 〉
통과 (0.27ms, 3.8MB)
테스트 4 〉
통과 (0.52ms, 4.03MB)
테스트 5 〉
통과 (0.57ms, 3.98MB)
효율성  테스트
테스트 1 〉
통과 (37.30ms, 12.2MB)
테스트 2 〉
통과 (56.86ms, 16.7MB)
테스트 3 〉
통과 (70.14ms, 19.5MB)
테스트 4 〉
통과 (79.22ms, 21.3MB)
테스트 5 〉
통과 (77.84ms, 21.2MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

너무 간단하지만 다른 사람들의 풀이를 보다보니 알게 된 것인데 이 문제의 원래 카테고리는 해시이다. 해시를 이용한 풀이는 다음과 같다. 

김준영 , 이상흥 , 전종구 , 장태익 , 박희제 외 5 명의 풀이입니다.

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> strMap;
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }
 
    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem))
        {
            answer = elem;
            break;
        }
        else
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}