[C++] 완주하지 못한 선수

1. 정렬해서 풀기

#include <string>
#include <vector>
#include <algorithm>	//sort

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    //정렬
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    
    int i = 0;
    for(; i < completion.size(); i++) {
        if(participant[i] != completion[i]) {
            break;
        }
    }
    return participant[i];
}

 

algorithm에서 지원하는 sort 기능이 필요하다.

2. 해시로 풀어보기

해시 기억이 안나서 다시 공부를 하고 왔다. 

https://getcomponent.tistory.com/105

해시(Hash) 간단하게 정리

C++에서 해시 테이블을 사용하기 위해서는 STL 중 unordered_map을 사용한다고 한다.

map과의 차이점은, 정렬의 유무 차이이다. 

기본적으로 map의 탐색 시간은 O(logn), unordered_map의 탐색 시간은 O(1)이다.

많은 자료를 저장하고, 검색이 주를 이룰 경우, unordered_map이 vector나 list보다 효율적이게 된다.

 

세번째 케이스인 참가자 ["mislav", "stanko", "mislav", "ana"] 완주자 ["stanko", "ana", "mislav"] 로 고려해본다.

 

선언하기

#include <unordered_map>

unordered_map<key_type, value_type> map;	//선언

unordered_map<string, int> map;	//이 문제의 경우

위 문제의 경우 key는 participant name,

value는 참가자 수로 지정하며 이후 검사에서 완주가 확인될때마다 값이 감소한다.

 

참가자 해시테이블 생성하기

map.insert(make_pair(key,value));
map.insert({key,value});
map[key] = value;

단일 쌍의 삽입은 위와 같이 이루어진다. key가 이미 존재하는 경우 삽입은 이루어지지 않는다.

이 문제는 참고로 동명이인이 존재한다! key의 중복 문제가 발생한다는 얘기임.

그렇기 때문에, 이미 존재하는 key라면 삽입하지 않고 key 값을 증가시키기만 한다.

이 문제는 참가자들 모두를 삽입해야하기 때문에 반복문으로 삽입해주기로 한다.

    unordered_map <string,int> map;
    
    for(string name : participant) {
        if(map.end() == map.find(name)) //중복되지 않는 key
            map.insert(make_pair(name,1));  //삽입
        else    //중복이 존재하는 key
            map[name]++;            
    }

map.find(name)은 해당 map에서 name에 해당하는 key가 존재한다면 해당 값을 반환한다.

존재하지 않는다면 해당 map의 가장 끝을 가키리는 map.end()를 반환한다.

따라서, if문에서 동명이인이 아니라면 insert, 동명이인이 있다면 해당 값의 value를 ++ 해준다고 보면 된다.

해시테이블 생성 후 map 의 구조

key(해시 변환 전으로 고려)	value
mislav	2
stanko	1
ana	1

↑ 해시테이블 생성 후 map 의 구조

 

**** 참고 ****

    unordered_map <string,int> map;
    
    for(string name : participant) {
            map[name]++;            
    }

이렇게 동명이인 검사를 해주지 않아도 된다.

map[key]++ 에서 해당 key가 존재하지 않는다면 value값을 default값인 0으로 선언해주기 때문이다.

 

참가자 해시테이블에서 완주자를 제외하기

participant를 모두 해시테이블에 저장했으니, 이제는 완주자 검사를 통해 value를 바꿀 시간이다.

    for(string name : completion) {
        map[name]--;
    }

완주자는 무조건 참가자이기 때문에 조건검사는 필요없다.

그냥 완주자마다 value값을 1씩 빼주자.

이렇게 되면 완주자는 value가 0이고, 완주하지 못한 한 사람은 value가 1이 된다. 

key(해시 변환 전으로 고려)	value
mislav	1
stanko	0
ana	0

↑ 완주자 제외한 후 map의 구조

 

value가 0이 아닌 key 찾아 반환하기

    for(auto element : map) {
        if(element.second > 0) {
            return element.first;
        }
    }

여기서 map의 element로는 key와 value로 이루어진 쌍이기 때문에, first로 key, second로 value에 접근이 가능하다.

element.second 값이 0보다 크다면 완주자가 아니므로 이름에 해당하는 first값을 반환하면 끝.

 

코드 정리

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map <string,int> map;
    
    for(string name : participant) {
            map[name]++;            
    }
    
    for(string name : completion) {
        map[name]--;
    }
    
    for(auto element : map) {
        if(element.second > 0) {
            return element.first;
        }
    }
}

 

 

 

해시를 처음 사용해봐서 익히는데 시간이 좀 걸렸다.