[level 1]완주하지 못한 선수 2차 풀이, hash, unordered_map

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

1차 풀이 방법

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

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

        } 
}

풀이방법

completion 원소로 <원소 ,개수> pair를 가지는 hash map를 만든다.

그 다음 participant의 원소와 개수를 비교해서 답을 찾는다.

이 때 find를 사용했는데

count(participant.begin(), participant.end(),elem2) != com_map.count(elem2)

이런 식으로 count를 활용해 바로 개수를 통해 답을 구해도 될 듯 하다.

 

배운 내용

• map이란 인덱스를 문자열로 받는 배열 ,  unordered_map, map이 있다.
• unorderd_map : hash map으로 구현된다.
  • 헤더 파일 : <unordered_map>
  • 해당 key가 존재 여부는 find(), count()를 통해
    • m.find(elem)
    • m.count(elem)
  • 삽입 시 m.insert()하고 수정 시 m[key] 방식으로 

 

2차 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(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(completion[i].compare(participant[i]) !=0 ) return participant[i];
    }
    return participant[participant.size()-1];
}

풀이 방법

hash를 사용하지 않고 sort를 사용한 방법이다. 

이름 순으로 정렬한 후 completion과 participant가 달라지는 순간을 찾아 리턴하는 방식이다.

 

수행시간

O(nlog₂n) : sort알고리즘을 사용해 정렬하는 시간이 보통 O(nlog₂n)이니까

 

 

 

참고 사이트

ordered_map : https://umbum.tistory.com/744

c++의 count, count_id : https://modoocode.com/262