[Programmers - lv01] 완주하지 못한 선수 (cpp / python)

완주하지 못한 선수

코딩테스트 연습 - 완주하지 못한 선수

 

문제 설명

participant에 있는 참가자들 중 completion에 없어 완주하지 못한 선수를 찾는 문제

문제 카테고리에 해쉬 라고 명시되어있지만 STL 도 익숙해질겸 <algorithm>의 find함수를 이용해서 풀어보았다. 결과는 역시 시간초과 해쉬구조가 왜 빠른지를 보여주는 문제였다.

문제 풀이

소스코드 : C++

틀린 코드 find함수를 이용한 풀이.

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    for(string player : participant){
        auto iter = find(completion.begin(), completion.end(), player);
        if(iter == completion.end()) answer = player;
        else completion.erase(iter);
    }
    return answer;
}

그렇다면 해쉬 를 쓰지않고는 풀 수는 없을까?

find함수만을 이용하여 문제를 해결하면 느린이유는 불필요한 탐색을 계속하기 때문이다. 그렇다면 탐색하지 않고 해결할 수 있는 방법을 생각해보면 정렬을 이용하면 시간 단축을 할 수 있다.

어짜피 단 한명의 선수가 남기 때문에 모든 참가자가 서로 다른 이름을 가지고 있다면 맨 마지막에 남을 것이고, 그렇지 않다면 participant[i] != completion[i] 인 경우이다.

#include<iostream>
#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 < completion.size(); i++){
        if(completion[i]!=participant[i]) return participant[i];
    }
    return participant.back();
}

해쉬 구조로 이루어진 unordered_multiset을 이용하여 문제를 풀면 다음과 같다. 여기서 multiset을 이용하는 이유는 문제에서 중복 을 허용하기 때문이다.

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_multiset<string> completetion_player;
    for(string s : completion) 
        completetion_player.insert(s);
    for(string s : participant){
        auto itr = completetion_player.find(s);
        if(itr != completetion_player.end()) completetion_player.erase(itr);
        else return s;
    }
}

물론 multiset을 이용하지 않고 map을 이용해도 풀 수 있다. (unordered_map과 map의 차이는 정렬안하고 하고 차이인데 구조가 좀 다르다. 나중에 포스팅하겠다. ) completion의 player들을 카운트하여 map의 value로 넣어주고 participant의 선수들을 탐색하여 깎아주다가 value가 -1이 되거나 찾을 수 없을때의 player를 반환해준다.

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string,int> completion_player;
    for(string s : completion) 
        completion_player[s]++;
    for(string s : participant){
        auto itr = completion_player.find(s);
        if(itr != completion_player.end()) {
            completion_player[s]--;
            if(completion_player[s]==-1) return s;
        }
        else return s;
    }
}

이렇게 여러가지 방식으로 풀어보는 이유는 간단한 level1의 문제지만 중복을 해결하는 과정과 문제를 여러가지 방식으로 해결할 수 있기 때문이다. 또한 이를 적용해서 다른 문제를 푸는데에 도움이 될 수도있다. 물론 모든 문제를 이렇게 풀어보면 좋겠지만... 시간도 너무 오래걸리고... ㅠㅜ

 

소스코드 : Python  

python은 정렬을 이용한 방식으로 해결했다.

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]