본문 바로가기
OLD_알고리즘/Programmers - 알고리즘

Programmers ] Level 1 - 완주하지 못한 선수

by 달승 2021. 1. 22.

 

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

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

programmers.co.kr

더보기

 

처음 코드

 

: sort한 후 비교하는 게 빠를 것 같다는 생각이 들었다.

#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++){
        for(int j = 0; j < participant.size(); j++){
            if(completion[i] == participant[j]){
                participant.erase(participant.begin() + j);
            }
        }
    }
    
    for(int i = 0; i < participant.size(); i++){
        if(participant[i] != " ") answer = participant[i];
    }
    
    return answer;
}

 

> 테스트 2번은 어떤 테스트 케이스인지 모르겠음...

 

두 번째 코드

* break 추가하니까 2번 맞음

#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++){
        for(int j = 0; j < participant.size(); j++){
            if(completion[i] == participant[j]){
                participant.erase(participant.begin() + j);
                break;
            }
        }
    }
    
    answer = participant[0];
    
    return answer;
}

 

* 효율성을 위한 코드

1차 sort 없앴을 때
2차 이중 for문을 없애야 할 것 같다.

 

* check하면서 풀었던 메모

 

 

🌱 정답코드

 

 

 

👍 Hash를 적용한 코드

출처

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem)) // 현재 맵에 elem 값이 없다면
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }
    // 11~17 : map에 없다면 ("완주자", 1)를 insert, map에 존재한다면 뒤의 숫자에 1을 더해주는 의미

    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem)) // 현재 맵에 elem 값이 없다면
        {
            answer = elem;
            break;
        }
        else // 중복된 이름 check
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}

댓글