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

programmers.co.kr/learn/courses/30/lessons/42576

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

---

문제풀이)

먼저 두 벡터 participant와 completion을 정렬을 해줍니다.

정렬을 해준뒤, 처음인덱스부터 completion의 사이즈까지 탐색을 하며, 다른부분이 생긴다면 해당 인덱스의 participant원소를 answer에 넣어주고, 끝까지 돌았는데도 모두 같다면, participant의 마지막 원소가 answer가된다.

 

ex) participant=["A","C","E","D","G"] / completion=["A","G","C","E"]

정렬 결과 participant=["A","C","D","E","G"] / completion=["A","C","E","G"]

for문을 돌리면 2번째 인덱스 "D"와 "E"가 다르기 때문에 완주하지 못한 선수는 "D"가 된다.

 

#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());
    int size=completion.size();
    for(int i=0;i<size;i++){
        if(participant[i]!=completion[i]){
            answer=participant[i];
            break;
        }
    }
    if(answer==""){
        answer=participant[size];
    }
    return answer;
}

---

<map을 이용한 방법>

<name,num>형식으로 completion안의 원소들을 넣는다. 처음넣을땐 num=1로, 동명이인이 나올땐 num++하는 방식으로 넣어준 뒤, participant를 돌며 해당이름이 맵에 없으면 그 이름이 answer, 있다면 해당 이름의 num을 1감소시킨다. 만약 감소시키고 음수로 떨어지게 되면 해당 이름이 answer가 된다.

 

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string,int> um;
    for(auto c:completion){
        if(um.find(c)==um.end())    um.insert(make_pair(c,1));
        else um[c]++;
    }
    for(auto c:participant){
        if(um.end()==um.find(c)){
            answer=c;
            break;
        }
        else{
            um[c]--;
            if(um[c]<0){
                answer=c;
                break;
            }
        }
    }
    return answer;
}