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

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

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

 

전체 코드 ( map을 이용한 풀이 방법 )

#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.insert(pair<string, int>(participant[i], 1));
        else
            m[participant[i]] += 1;
    }

    for (int i = 0; i < completion.size(); i++)
    {
        m[completion[i]]-=1;
    }
    
    
    for(auto iter = m.begin();iter!=m.end();iter++)
    {
        if(iter->second!=0)
        {
            answer=iter->first;
            break;
        }
    }


    return answer;
}

 

참가자(participant)의 이름을 이용해 map에 +1을 해주고

완주자(completion)의 리스트를 돌며 map에 -1을 해주었다.

또 다시 참가자(participant)를 돌며 0이아닌 참가자를 찾는다.

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<participant.size();i++)
    {
        if(i==participant.size()-1)
        {
            answer=participant[i];
            break;
        }
        else if(participant[i]!=completion[i])
        {
            answer=participant[i];
            break;
        }
    }

    return answer;
}

 

정렬을 이용하면 참가자가 완주를 했다면 두 벡터 동일한 위치에 동일한 이름이 있을것이다.

만약 참가자 i번째와 완주자 i번째 이름이 다르다면 참가자 i는 완주를 하지 못한 사람이다.

 

아래의 if문은 예외 처리로

만약 참가자의 맨 마지막에 미완주자가 있다면

완주자 벡터 i번째는 비어있을것이다. 자칫하면 null인 곳을 접근하므로 에러가 난다.

즉, i가 참가자 벡터의 크기 마지막이라면 안봐도 이 참가자가 미완주자일 것이다.

(ex, 참가자(A B C), 완주자(A B) -> 미완주자 C

if(i==participant.size()-1)
{
        answer=participant[i];
        break;
}

확실히 정렬을 이용한 방법이 빠르다.