[C++] 프로그래머스 레벨 1 - 완주하지 못한 사람 구하기

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

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

모범 답안이다. 내가 푼 건 아니고, 효율성 통과를 못하다가 해시 항목인 걸 보고 뭔가 이상함을 느껴서 답안을 찾아보았다. ㅋㅋ;

boycoding.tistory.com/226

[프로그래머스] 완주하지 못한 선수, map과 unordered_map의 차이

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

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

 

원래는 unordered_map을 사용했는데, 내가 배운 STL에는 map과 multimap, set, multiset 밖에 없어 그냥 자료구조만 map으로 수정했다. 크게 문제는 없더라.

여기서 name : participant가 생성자에서 대입할 때 봤던 형태인 것 같은데, 잘 모르겠다.

map은 key와 value(파이썬의 딕셔너리처럼)를 가지는 자료구조인데, key를 사람이름(string) 주고, value를 포함된 갯수로 생각한다.

이 코드 작성하신 분 코드에서 고수의 냄새가 솔솔 난다. 내가 못하는것도 있겠지만서도.,.

 

 

 

 

이게 내가 짠 코드이다. 아마 find()에서 순차적으로 탐색을 하니 N번 탐색했을 것이고, 그 작업을 completiond의 갯수인 N-1번 했을 테니 N^2이 되어 효율성 통과를 못한 것이 아닌가 생각이 된다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer;
    
    vector<string>::iterator iter;
    
    for(int i = 0; i < completion.size(); i++)
    {
        vector<string>::iterator iter2 = find(participant.begin(), participant.end(), completion[i]);
        if(iter2 != participant.end())
        {
            participant.erase(iter2);
        }
        else
            return *iter2;
    }
    
    answer = participant.front();
    
    return answer;
}