Imeamangryang | 게임 개발 기록

문제 링크

접근 방법

참가자 수는 완주자보다 1명이 많다.

즉, participant - completion 을 했을 때 남는 사람이 완주하지 못한 선수이다.

단순한 리스트 연산으로도 가능하지만 해시도 이용가능하다.

풀이 코드

C++

#include <string>
#include <vector>
#include <unordered_map> // hash를 위한 unordered_map

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
   string answer = "";
   unordered_map<string, int> hash; // Hash 테이블 선언

   // 각 참가자 이름을 해시 테이블에 저장
   for (const auto& name : participant) {
       hash[name]++;
   }

   // 완주한 참가자 이름을 해시 테이블에서 제거
   for (const auto& name : completion) {
       hash[name]--; // Decrement count for each completion
   }

   // 해시 테이블에서 남아 있는 참가자 이름 찾기
   for (const auto& entry : hash) {
       if (entry.second > 0) { 
		   answer = entry.first; // 0 이상인 경우, 즉 남아 있는 참가자 이름을 찾음
           break;
       }
   }

   return answer;
}

해설

🔍 코드 설명

C++

// 참가자 이름을 해시 테이블에 저장
for (const auto& name : participant) {
    hash[name]++;
}

participant 벡터를 순회하며 각 이름의 등장 횟수를 해시 테이블(unordered_map)에 저장한다.

동명이인이 있을 수 있기 때문에 단순한 존재 여부 체크가 아닌 카운팅이 필요하다.

c++

// 완주자의 이름을 해시 테이블에서 감소
for (const auto& name : completion) {
    hash[name]--;
}

완주한 사람의 이름에 대해 카운트를 1씩 감소시킨다.

모든 완주자는 등장 횟수가 맞춰지면서 0이 되며, 완주하지 못한 사람은 1이 남는다.

C++

// 남은 사람이 완주하지 못한 사람
for (const auto& entry : hash) {
    if (entry.second > 0) {
        answer = entry.first;
        break;
    }
}

해시 테이블을 순회하면서 값이 0이 아닌 사람을 찾아 반환한다.

단 한 명만 완주하지 못했기 때문에, 조건을 만족하는 순간 break 해도 된다.

다른 풀이

text

#include <string>
#include <vector>
#include <algorithm> // Include for sort function  

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 < participant.size(); i++)
    {
        if (i == participant.size() - 1)
        {
            answer = participant[i];
            break;
        }
        else if (participant[i] != completion[i])
        {
            answer = participant[i];
            break;
        }
    }

    return answer;
}

기본적으로 정렬과 단순 비교를 이용한 방법도 가능하다.