개발기록장

완주하지 못한 선수

6 min read

문제 링크
난이도 : Lv. 1

문제 내용

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

입력

[“leo”, “kiki”, “eden”]

[“eden”, “kiki”]

출력

leo

문제 분석

난감함.

참가자 중에 동명이인이 있을 수 있어서 그냥 set을 쓰기엔 좀 그럼..

딱 한사람만 다르니까 그냥 배열을 이어버린 다음에 set으로 해볼까

작성한 코드

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    unordered_multimap<string,bool> m_map;
    for(const string& com : completion) m_map.insert(pair<string, bool>(com, true));
    for(const string& part : participant) {
        unordered_multimap<string,bool>::iterator it = m_map.find(part);
        
        if(it == m_map.end()) return part;
        m_map.erase(it);
    }
    
    return m_map.begin()->first;
}

중복이 가능한 multimap을 썼음

  1. 멀티맵에 완주자를 넣음
  2. 참가자 이름대로 한명씩 검색함
    1. 검색결과가 안나오면 그 사람이 완주 못한거니까 바로 리턴
    2. 중복이 가능하다고 했기 때문에 iterator를 기준으로 erase함 (값으로 지워버리면 다 지워지니까)
  3. 동명이인이 2명 있는데 한명만 완주하면 아마 if문에 안걸릴 것 같아서 return문을 for문 밖에도 해줬음

이거 만드는데도 오래걸렸음.. 말도안돼

c++ 반복자는 [ ) 형태를 띈다..

따라서 검색결과가 없으면 map.end()를 냄

검색 결과가 마지막에 있더라도 map.end()가 나오지는 않음 왜냐면 [ ) 니까 애초에 map.end()는 포함이 안되는거임!! 그게 나오면 그냥 없단뜻임..

stl 구조들을 별로 안써봐서 이해도 이슈가 있었음..

우수 코드 분석

이 문제 우수 코드가 하나는 AI 하나는 사람

// deepseek가 짜준 코드
#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> m_map;
 
    // 완주자 명단을 맵에 추가
    for (const string& com : completion) {
        m_map[com]++;
    }
 
    // 참가자 명단을 맵에서 제거
    for (const string& part : participant) {
        m_map[part]--;
        if (m_map[part] < 0) {
            return part;  // 완주하지 못한 선수 반환
        }
    }
 
    // 문제가 없는 경우 (문제 조건상 여기는 실행되지 않음)
    return "";
}

딥시크의 주장 : 굳이 multimap을 할 필요는 없다. 그냥 같은 이름의 완주자면 int로 추가해버리면 됨!

나는 멀티맵 글을 봤다보니까 [] ← 멀티맵이 이걸로 접근 안된다는거만 알고있었음

근데 그냥 맵 써버리면 [] 로 하면 됨

심지어 값이 없는 상태에서 저렇게 하면 자동으로 기본값인 0이 들어감!!

그러니까 m_map[com]하면 일단 {com, 0} 쌍으로 하나 들어가고 거기서 ++ 하니까 value가 1이 됨

그럼 동명이인 체크를 굳이 multimap을 안해도 됨

왜냐? 같은 이름의 사람이 2명 3명 되면 알아서 value가 늘어나니까

그리고 m_map[part]— 하면 만약에 사람이 없으면 초기값 0에서 -1되어서 <0이 성립됨

// 어느 고수분의 코드
#include <string>
#include <vector>
#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());
    for(int i=0;i<completion.size();i++)
    {
        if(participant[i] != completion[i])
            return participant[i];
    }
    return participant[participant.size() - 1];
    //return answer;
}

그냥 정렬해서 풀어버리심..

정렬한 다음에 안맞으면 그 사람이 완주 못한거임 ..

그래프 뷰