C++ 완주하지 못한 선수(프로그래머스)

프로그래머스_완주하지 못한 선수

https://programmers.co.kr/

 

해시

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

참가자 중 완주하지 못한 사람의 이름을 출력

​

방법

1. completion의 길이는 participant의 길이보다 1 작습니다.

2. 참가자 중에는 동명이인이 있을 수 있습니다.

 

결과

참가자 중 완주하지 못한 사람의 이름을 출력

 

1. 통과하지 못한 코드

#include <string>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    std::sort(participant.begin(), participant.end());
    std::sort(completion.begin(), completion.end());
    for (int i = 0; i < participant.size(); i++)
    {
        bool bRet = false;
        string strName = participant.at(i);
        for (vector<string>::iterator iter = completion.begin(); iter != completion.end(); iter++)
        {
            if (strName.length() != string(*iter).length())
                continue;
            if (strName == *iter)
            {
                completion.erase(iter);
                bRet = true;
                break;
            }

        }
        if (!bRet)
        {
            answer = strName;
            break;
        }

    }

    return answer;
}

 

정확성 테스트는 통과하였지만 효율성 테스트에서는 시간 초과.

- 나름 비교 횟수를 줄이기 위해 찾은경우 completion Vector의 인자를 삭제하는 코드를 넣어봤지만 시간 초과 발생

 

2. 통과한 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    bool bRet = false;
    for (int i = 0; i < completion.size(); i++)
    {
        string strName = participant.at(i);
        string strCon = completion.at(i);
        if (strName != strCon)
        {
            return strName;
        }
            
    }
    return participant.back();
}

두개의 Vector를 정렬하여 한번만 순회하여 다른경우 return 하도록 변경

- 한번만 돌면되며 for문에서 return이 되지않는 경우 맨 마지막 참가자가 완주하지 못했으므로 마지막 참가자의 이름을 전달

 

 

후기

1번 코드로만 쉽게 생각하여 5분이면 풀겠네하고 도전했지만 효율성 테스트에서 고민하다 20분이나 걸려버린 문제!