완주하지 못한 선수 C++,Python(해시)[프로그래머스]

문제 주소입니다.

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

프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

예시

participant	completion	return
[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

2. 문제풀이

---

이 문제는 프로그래머스 해시 1레벨 문제로 쉬운 난이도입니다. 해시를 몰라도 벡터를 이용해서 풀 수 있을 정도로 간단합니다. 해시를 이용한 문제 풀이와 벡터를 이용한 풀이 2가지를 해보겠습니다.   map은 key 와 value를 쌍으로 사용하는 자료구조입니다. key를 이용하여 value를 찾는 건데요​ 일종의 전화번호부와 같습니다. 김 아무개라는 key로 접근하면 휴대폰 번호인 value가 나오는 것처럼 말이죠! 그럼 여기서 전화번호 대신 count를 집어넣는 방식으로 처리를 합니다. 출발을 했으면 1명이 시작했다는 의미로 +1을 하고 완주를 하면 뛰는 사람이 줄어들었으므로 -1을 합니다. 위의 과정을 모두 거쳤다면 map을 한번 순회를 합니다. 완주를 했을 경우 이름으로 접근 시 0이라는 값이 나올 테고 완주를 못한 사람은 1이 될 것입니다. 이때 1인 사람을 반환하면 끝나는 문제입니다. 해시를 이용하는 이유 : 접근 속도가 빠르다. Python의 경우 딕셔너리를 이용하여 풀면 된다. ​ 벡터를 이용한 솔루션은 정렬 방식입니다. 완주를 하지 못한 사람은 한 명밖에 없기 때문에 정렬을 할 경우 참가자와 완주자가 다른 부분이 나오면 그 사람이 완주를 못한 사람인 것입니다. 위의 경우에도 걸리지 않았다면 비교는 완주자 기준으로 하기 때문에 참가자 제일 마지막 사람이 미완주자가 되는것입니다. 장점 해시를 몰라도 풀 수 있다. 구현을 편하게 할 수 있다. 단점 : 정렬을 해야 하므로 비용이 많이 든다.

 

---

3. 소스코드

3.1 파이썬

def solution(participant, completion):
    answer = {}
    for i in participant:
        answer[i] = answer.get(i, 0) +1
    for j in completion:
        answer[j] -= 1
    for k in answer:
        if answer[k] : return k

 

3.2 C++ 딕셔너리

#include <vector>
#include <string>
#include <unordered_map>//해쉬맵 사용
#include <iostream>//메인 출력용
using namespace std;
 
string solution(vector<string> participant, vector<string> completion)
{
    string answer = "";
    unordered_map<string, int> temp;
    for (string name : participant)
    {
        //해쉬테이블에 key값으로 name을 주고 값을 더함
        temp[name]++;
    }
    for (string name : completion)
    {
        //name key로 접근하여 값을 감소
        temp[name]--;
    }
    //처음부터 해쉬테이블 순회
    for (auto pair : temp)
    {
        //해쉬테이블의 2번째값이 0보다 크다면
        if (pair.second > 0)
        {
            //answer에 해쉬테이블 key값을 넣음
            answer = pair.first;
            break;
        }
    }
    return answer;
}
 
int main() {
    vector<string> a = { "marina", "josipa", "nikola", "vinko", "filipa" };
    vector<string> b = { "josipa", "filipa", "marina", "nikola" };
    cout << solution(a, b) << endl;
    return 0;
}

C++ vector

#include <vector>
#include <string>
#include <iostream>//메인 출력용
#include <algorithm>
using namespace std;
 
 
//정렬을 이용한 솔루션
string solution2(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 (participant[i] != completion[i])
        {
            //다른 이름값을 리턴
            return participant[i];
        }
    }
    //위의 조건에 걸리지 않았다면 참가자중 제일 마지막값 리턴
    return participant[participant.size() - 1];
}
 
int main() {
    vector<string> a = { "marina", "josipa", "nikola", "vinko", "filipa" };
    vector<string> b = { "josipa", "filipa", "marina", "nikola" };
    cout << solution(a, b) << endl;
    return 0;
}

 

---

C++ map

벡터와 정렬

python 딕셔너리