완주하지 못한 선수 - 프로그래머스, C++

 

 

- 문제 풀이

오늘은 해시 문제를 풀어보았다.

수업시간에 "해시"라는 개념에 대해 명확히 짚고 간 적은 없어서 먼저 해시의 개념부터 공부했다.

해시(Hash)는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다.

데이터를 저장하거나 데이터의 위치를 찾고자 할 때 해시를 사용하여 더 빠르게 자료 구조를 탐색, 삽입 등을 할 수 있다.

!! c++에서의 해시테이블은 파이썬에서의 딕셔너리와 같이 "키"로 접근에 그에 연결된 "값"부분의 값을 변경할 수 있음 !!

!! 해시테이블과 딕셔너리에서는 동일한 "키"를 여러개 저장할 수 없음, 키는 서로 같을 수 없음을 알기 !!

 

 

- 코드

처음에 작성한 코드는 다음과 같다.

정확성에서는 100%의 점수를 받았지만 효율성에서는 실패의 결과를 받았다.

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    int arr[100000] = {0,};
    
    for(int i=0; i<participant.size(); i++) {
        bool same = false;
        for(int j=0; j<completion.size(); j++) {
            if(participant[i]==completion[j] && arr[j]==0) {
                same = true;
                arr[j] = 1;
                break;
            }
        }
        if(!same){
            answer = participant[i];
            break;
        }
    }
    
    return answer;
}

 

 

역시 위의 코드에서는 해시를 사용하지 않고 배열을 사용했기 때문에 효율성 문제가 발생하는 것이었다.

효율성 문제를 해결하기 위해서는 해시를 사용해 다음과 같이 구현해야 했다.

!! # include <unordered_map>을 사용 !!

1번 코드(https://mungto.tistory.com/193)

#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;
}

2번 코드(https://coding-grandpa.tistory.com/89)

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

using namespace std;

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

    for (auto player : completion)
        map[player]--;

    for(auto player : participant)
        if (map[player] > 0)
        {
            answer = player;
            break;
        }
    return answer;
}

int main(void)
{
    vector<string> part = {"leo", "kiki", "eden"};
    vector<string> comp = {"eden", "kiki"};
    cout << solution(part, comp);
    return 0;
}

#include <algorithm>을 사용하여 해결하는 방법도 있으니 나중에 알아보도록 하자.