[완주하지 못한 선수] - multiset/ hash_set ★☆☆☆ / 복습 ○

[ 문제 ] : https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

---

[ 문제 접근 ]

 

우선 중복이 가능하다고 했으니 multiset을 사용할 것이고,

participant 를 전부 multi_set에 넣어주고, completition 과 multi_set을 비교하면서 지워줘야겠다고 판단.

 

---

[ 첫번째 풀이 ]

 

#include <string>
#include <vector>
#include<set>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    multiset<string> m_set;
    
    for(int i=0;i<participant.size();i++){
        m_set.insert(participant[i]);
    }
    
    for(size_t i =0;i<completion.size();i++){
        if(m_set.find(completion[i]) != m_set.end()){
            m_set.erase(completion[i]);
        }
    }
    
    answer = *(m_set.begin());
    
    return answer;
}

 

m_set 에 참가자 전부 넣어주고 완주자 목록이랑 비교하면서 지워나가고, 마지막 참가자 목록에 있는 사람이 낙오자!

 

라고 풀고 싶었다.

 

그러나 실패..  문제 풀면서 메모라 한도 초과는 처음 겪어본다..

 

 

우선 뭐가 잘못됐는지 생각해봤다.

 

문제의 카테고리는 hash라 unordered_set이나 unordered_map을 써야하는건가? 싶기도 했지만 그냥 multi set으로도 풀 수 있을것만 같았다.

 

메모리는 그렇다 치더라도 우선 테스트 결과도 전부 성공하지 못했기에 로직에 문제가 있음을 알고 한참을 고민했다.

 

그러다 erase 부분에서 내가 착각을 하고 있었다는것을 알게 되었다.

 

multiset 변수 p에 "ab"가 8개가 들어있다면 p.erase("ab") 을 하면은 "ab"가 하나만 지워질것이라고 착각했다.

 

하지만 실행해본 결과  8개의 "ab"가 전부 지워진다.  급하게 multiset의 erase 함수를 찾았다.

 

 

erase 함수는 총 세개의 원형이 있다.

 

1. erase( iterator pos)  -> pos의 elem 지우고 다음 iterator 값 리턴.
2. erase( iterator first, iterator last)  -> first~last 까지 지우고 다음 iterator 값 리턴.
3. erase( const key_type& key) -> key와 같은 값 전부 지우고, 지운 elem 개수 리턴.

※ 물론 리턴 값을 받을 좌측값이 없이 erase( ) 만 실행하면 리턴되는게 없다.

 

- 1. erase("원소이름직접전달") => 이 방식을 선택하면 중복된 모든 원소 삭제/ 되기 때문에 아래의

- 2. erase("이터레이터전달") => 이터레이터가 가리키는 원소 하나 삭제/ 이 방식으로 구현하는게 좋을 것 같았다.

multiset에 "mislav"가 두개 존재한다면, mulitset.erase("mislav") 는 "mislav" 두개를 전부 지우게 된다.
나는 "mislav" 를 한번 지워야 하기에 erase(pos) 인 두번째 방법이 좋아 보인다.

 

 p.erase(p.find(*iter));

 

p.find(*iter); 

 

-> 찾는 원소가 없으면 p.end() 를 반환하는데 p.erase(p.end()) 를 해주면 아무 일도 발생하지 않는다.

-> 찾는 원소가 있으면 해당 원소의 iterator를 리턴하고 p.erase(해당 원소 iter) 하게 되니깐 그 원소만 삭제된다.

 

 

#include <string>
#include <vector>
#include <set>

using namespace std;
/*
- 문제 : [완주하지 못한 선수] https://programmers.co.kr/learn/courses/30/lessons/42576
- 접근 방식 : 
	문제 카테고리가 hash라 unordered_map을 사용하려고 생각하였으나,
	참여 선수가 최대 100,000 이니 삽입의 시간복잡도가 O(logn)인 set/map으로도 가능하다고 판단.
	추가로 value 값을 이용할 필요가 없다고 생각해서 중복이 가능한 multiset을 사용.
- 시간 복잡도 : O(nlogn) ?
*/


string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    multiset<string> m_set;
    for(int i=0;i<participant.size();i++){  // O(n)
        m_set.insert(participant[i]);       // O(logn)
    }
    
    // 완주한 사람들의 이름을 뺀다.
    for(size_t i =0;i<completion.size();i++){
        m_set.erase(m_set.find(completion[i]));
    }
    
    // 마지막에 m_set에 남은 한 사람이 완주하지 못한 사람.
    answer = *(m_set.begin());
    
    
    return answer;
}

---

[ 다른 사람 풀이 ]

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

using namespace std;

/*
- 문제 : [완주하지 못한 선수] https://programmers.co.kr/learn/courses/30/lessons/42576
- 접근 방식 : 
	unordered_map을 사용
- 시간 복잡도 : O(n) 
*/

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	unordered_map<string, int> d;

	// unordered_map 이나 map 같은 경우, 없는 key 값을 추가하면 자료형의 default 값이 들어가기때문에 d["lena"] 해주면 key 값으로 0이 들어간다.
	for (auto& elem : participant) d[elem]++;

	// 완주한 사람들의 이름을 뺀다.
	for (auto& elem : completion) d[elem]--;

	//각 참여자 이름에 해당하는 value는 0 아니면 1이 되어있는데 값이 1인 사람이 완주하지 못한 사람이다.
	for (auto& elem : d) {
		if (elem.second > 0) {
			answer = elem.first;
			return answer;
		}
	}
}

 

---

[ Key Porint ] 

- 없는 key값을 추가하면 자료형 default 값이 들어간다. d["lena"] 라고 하면은 d 는 빈 unordered_map인데 lena가 들어가면서 value는 0으로 들어간다.