코딩테스트 | (c++) 프로그래머스 : 완주하지 못한 선수

✅문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

❕ 제한사항

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

🎹📢입출력 예제

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

✍풀어보기

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort함수를 사용하기 위한 라이브러리
#include <unordered_map> // 중복을 허용하지 않고, 정렬 없이 저장하는 공식 표준 해시맵이다.

using namespace std;

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

    // unordered_map<key type, value type>
    unordered_map<string, int> members;

    // key : 참가한 선수 이름, value : +1
    for (auto par : participant) members[par]++;

    // key : 완주한 선수 이름, value : -1
    for (auto com : completion) members[com]--;

    // 해시 맵을 순회하여 value값이 0인 선수를 찾아서 반환 값에 대입한다.
    for (auto member : members)
    {
        // first : key 값, second : value 값
        if (member.second > 0) {
            answer = member.first;
            break; // 완수자와 참가자의 길이는 1차이 즉, 미완주자는 한명밖에 없으므로 종료
        }
    }

    return answer;
}

// vector만을 이용해서 푸는 경우
string solution(vector<string> participant, vector<string> completion, bool isVector) {
    // 빠른 비교를 위해 참가자 및 완료자 목록을 정렬해준다.
    // 같은 이름은 같은 인덱스에 배치된다.
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++)
    {
        // 참가 선수가 완주 선수가 이름이 같은지 비교한다.
        // compare() 문자열 비교 같으면 0 아니면 -1 또는 1을 내뱉는다.
        if (participant[i].compare(completion[i]) != 0) {
            return participant[i];
        }
    }

    // 완주하지 못한 선수가 반드시 있으므로 비교해서 찾지 못했으면
    // 정렬된 후의 마지막 선수가 미완주 선수이다.
    return  participant[participant.size() - 1];
}


int main() {
    
    // unordered_map을 사용하여 푼 함수를 이용
    cout << solution({ "leo", "kiki", "eden" }, { "eden", "kiki" }) << endl;

    cout << solution({ "marina", "josipa", "nikola", "vinko", "filipa" }, 
        { "josipa", "filipa", "marina", "nikola" }) << endl;

    cout << solution({ "mislav", "stanko", "mislav", "ana" }, 
        { "stanko", "ana", "mislav" }) << endl;

    // vector를 응용하여 푼 함수를 이용
    cout << solution({ "leo", "kiki", "eden" }, { "eden", "kiki" }, true) << endl;

    cout << solution({ "marina", "josipa", "nikola", "vinko", "filipa" }, 
        { "josipa", "filipa", "marina", "nikola" }, true) << endl;

    cout << solution({ "mislav", "stanko", "mislav", "ana" }, 
        { "stanko", "ana", "mislav" }, true) << endl;

    return 0;
}

처음 5분만에 "다풀었다~!"라는 착각으로 결과를 제출해보니, 정확성 테스트는 통과하는데 효율성에서 실패를 맛봤다. 내가 처음 풀었던 방식은 이중 반복문을 통해서 참가자 목록과 완주자 목록을 비교하면서 목록에서 제거하는 작업으로 진행했었다.. 그래서 생각보다 쉽다고 생각했는데 이렇게 푸는게 아니더라! 아는만큼 보인다고 했던가 다른 방법은 생각도 안해봤다. 그냥 기존에 있는 제한된 상태에서 응용하려고만 했을 뿐!! 함께 실패한 코드를 살펴보도록 하자.

정확성 테스트는 통과했지만, 효율성에서 탈락한 코드

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

    // 참가한 선수 목록과 완주한 선수 목록을 비교하여
    // 완주한 선수를 두 목록에서 뺀다. 그리고 완주하지 못한 선수만 남는다.
    for (int i = 0; i < participant.size();)
    {
        bool isParticipantErase = false;
        for (int k = 0; k < completion.size(); )
        {
            // 효율성을 위해 한글자만 먼저 비교
            if (participant[i][0] == completion[k][0]) {
                // 문자열 비교 같으면 0 아니면 -1 또는 1을 내뱉는다.
                if (participant[i].compare(completion[k]) == 0) {
                    participant.erase(participant.begin() + i);
                    completion.erase(completion.begin() + k);
                    isParticipantErase = true;
                    break;
                }
                else k++;
            }
            else k++;
            
        }
        if(isParticipantErase == false)
            i++;
    }

    answer = participant[0];

    return answer;
}

---

참고 자료 및 사이트 (감사합니다)

• https://programmers.co.kr/learn/courses/30/lessons/42576