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

 

안녕하세요? 수구리입니다.

이번 문제는 프로그래머스의 해쉬 part에 있는 문제입니다.

사실 해쉬 부분에 있어 해쉬로 풀어도 가능하지만, 저는 좀 다르게 풀었습니다.

문제는 아래 링크에 있습니다.

 

 

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

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

코딩테스트 연습 - 없는 숫자 더하기

 

 

[ 나의 풀이 ]

#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 (participant[i] != completion[i]) {
            answer = participant[i];
            break;
        }
    }
    
    return answer;
}

 

[ 설명 ]

1. 입력이 participant(string)과 completion(string) 두 벡터입니다.

2. participant 배열은 참여자의 이름이, completion 완주한 사람의 이름이 저장되어있습니다. 초기 answer에는 빈 문자열로 초기화해주었습니다.

3. 벡터에는 sort라는 내장 함수가 존재합니다. 이를 이용해서 각각의 벡터를 알파벳순으로 정렬해줍니다.

4. 반복문을 통해서 두 배열을 비교 순회하여 만약 서로 다른 이름이 발견이 되면 그때의 참여자 이름이 완주하지 못한 선수의 이름이 되는 것입니다.

5. 반복문을 빠져나오고 answer를 return 합니다.

 

 

 

[ 실행 결과 ]

굳이 해시를 이용해서 풀지 않아도 정확성과 효율성이 만점이 나오네요!

 

다음으로는 다른 사람의 풀이를 살펴보도록 하겠습니다.

unorderd_map을 사용한 풀이입니다.

 

[ 다른 풀이 ]

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion)
    {
    	// 만약 map에 key값이 없다면!
        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;
}

 

 

[ 코드 설명 ]

unorderd_map 자료구조를 사용한 모습입니다.

unorderd_map은 순서 즉, 정렬이 없이 저장된 map의 형태로 정렬이 필요 없는 경우 훨씬 성능이 빠릅니다.

데이터가 N개일 때, map과 unorderd_map의 탐색 속도는

map은 O(log N) , unorderd_map은 O(1)입니다.

위의 주석 부분을 보면. end() 메서드를 사용했는데 이 메서드는

자료의 마지막 값의 다음 값인 빈 iterator의 메모리를 반환하는 메서드입니다.

마찬가지로. find() 메서드도 마찬가지로

iterator를 반환하는데 없다면 빈 iterator를 반환합니다.

따라서, 첫 if문에서 Key 값이 있다면 Key값을 추가하고, 있다면 Key값의 value를 증가시켜줍니다.