[프로그래머스 LV 1] 완주하지 못한 선수 C++

programmers.co.kr/learn/courses/30/lessons/42576

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

 

과거에 제가 프로그래머스에서 제일 처음 풀어본 문제입니다..

그때 진짜 손도 못 대고 뭐야 이걸 어떻게풀어 너무 어렵잖아...!! 라고 느꼈었는데..

 

한 한달동안 알고리즘문제만 한 백문제 가까이 풀다보니 레벨 1 문제는 정말 쉽게 느껴지네요 

확실히 PS는 하면 할 수록 느는것 같습니다.

 

총 두가지 풀이법이 보였습니다.

1. 백터 풀이법

-참가자 명단과 완주자명단을 오름차순 정렬 한 후 각각을 비교하며 완주하지 못 한 선수를 찾는방법

 

2. 해시 풀이법

-애초에 주제가 해시이니만큼(풀이는 개인적으로 백터풀이법이 훨씬 쉽습니다)

해시맵을 만든 후 완주자의 이름에 value를 1 추가해줍니다.

그 후 참가자명단을 key로 나온 값을 1씩 빼주고

결국 음수가 된 key가 완주하지 못 한 선수가 됩니다.

 

 

 

 

 

백터 버전

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#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());       for (int i = 0; i < participant.size(); i++) {         if (participant[i] != completion[i])             return participant[i];     }       return participant.back();     } Colored by Color Scripter

cs

 

 

해시 버전

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> map;
    //완주자 명단을 넣고 값을 1 상승
    for (auto elem : completion) 
        map[elem] ++;
 
    //참가자 명단을 넣으며 값을 1 하락
    //완주자 명단에 없었던 값은 음수로 떨어지게됨
    //동명이인 있을경우에도 마찬가지
    for (auto elem : participant) {
        map[elem]--;
        if (map[elem] < 0)
            answer = elem;
    }    
    return answer;
}