[프로그래머스 Level1 해시] 완주하지 못한 선수

문제 

문제 풀이

(1) 해시 사용

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
//마라톤선수들이 마라톤에 참여했다. 
//단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주한다.

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    //참여자에 없는 원소를 반환해야 한다.
    unordered_map <string, int> participants;
    
    for(string name : participant){
        ++participants[name];
    }
    
    for(string name : completion){
        --participants[name];
    }
    
    for(auto pair : participants){
        if(pair.second > 0){
            
            return pair.first;
        }
    
    }
    
    
    return answer;
}

완전 간단한 문제이다. 

두개의 배열에서 없는 배열원소를 반환하는 문제인데, 

이중 for문을 이용하여 구현하려고 했다.

그러기엔 시간복잡도가 커져서 해시문제인 만큼, 해시로 풀려고 했으나 해시경험과 지식이 부족해

해시 개념과 unordered_map 개념을 익혔다.

https://bohyeonstudy.tistory.com/101?category=964765 

Hash 개념 정리, std::unordered_map

 

(1) 향상된 for문을 이용해 참여자벡터원소를 map에 저장.

++ map[ key ] 으로 value값을 1로 저장한다. 

 

(2) 향상된 for문을 이용해 완료자벡터원소가 key인 경우, value값 수정

 

(3) map에 남아있는 value 값 반환하기위해 first, second 이용

for (auto pair : participants) { 
	if (pair.second > 0) 
	{ 
    	return pair.first; 
	} 
}

 

*향상된 for문, auto 익숙해지기

 

(2) sort 이용

#include <string>
#include <vector>
#include <stack>
#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());

//ABC , AC
    int size = completion.size();
    for(int i =0;i<size;i++){
        if(participant[i] != completion[i])
            return participant[i];
    }
    
    
    return participant[size];
}

sort를 이용해서 비교횟수를 줄이려고 했으나, 

예외처리 부분에서 실패했었다. 

다른 사람의 코드를 보고 깨달았다. 나중에는 좀 더 예시를 많이 들어보고 코드 짜기!