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

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

프로그래머스

 

크게 두가지 풀이가 있다

1. 정렬 사용

2. 해시맵 사용

 

-> 분류상으로 해시 안에 있어서 해시맵을 풀긴 했는데.. 이 문제를 그냥 처음봤을때는 정렬을 사용했을것같다!

왜 해시맵으로 풀라는지.. 시간복잡도를 생각해봐야겠다.

 

1. 정렬

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

 

string vector를 그대로 sort하면 사전순으로 정렬된다.

 

문제에서 딱 한명만 완주를 못했다고 하니까 participant랑 completion은 정확히 한명만 차이난다

== 정렬했을 때, 완주못한 한명만 빼면 무조건 똑같이 정렬된다!!

 

participant = [a, a, b, b, c, c, d]

completion = [a, b, b, c, c, d]

=> 이런 상태에서는 정답이 "a"가 된다.

 

그냥 앞에서부터 다른거 확인하면 됨

이 때 중요한건,, 정답을 찾으면 for문을 더이상 반복하면 안되는것!!! 무조건 정답 다음부터는 달라지기 때문이다.

 

 

효율성이 개쓰레구만

 

2. 해시맵

C++에서 해시맵은 <unordered_map>이다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string, int> comps;
    
    for(int i = 0; i<completion.size(); i++)
    {
        if(comps.find(completion[i]) == comps.end())
        {
            comps[completion[i]] = 1;
        }else{
            comps[completion[i]]++;
        }
        
    }
    
    for(int i = 0; i<participant.size(); i++)
    {
        if(comps.find(participant[i]) == comps.end())
        {
            answer = participant[i];
            break;
        }
        
        comps[participant[i]]--;
        
        if(comps[participant[i]] < 0)
        {
            answer = participant[i];
            break;
        }
    }
    
    return answer;
}

주요 아이디어는 해시맵은 find할 때 시간복잡도가 O(1)이라는 점이었다.

완주한 사람 명수를 해시맵에 넣고

-> 참여한 사람을 하나씩 지워가면서 명수가 음수가 됐을 때(혹은 없을 때) 정답을 뽑아낸다!

 

주의할점은 동명이인이 있을 수 있다는 점이어서..

단순히 find로 해시맵에 존재하는지 아닌지가 아니라, 동명이인중 몇명이 통과했는지를 판별하는것이 중요했다.

정렬보다는 빠른것을 볼 수 있었다!

 

3. 시간 비교

https://blockdmask.tistory.com/178

[C++] sort algorithm 정리 및 예시

algoritm 헤더파일에 있는 sort는 퀵정렬을 사용한다 == nlogn

-> 맨 처음 두번 정렬하고 (2nlogn) + 마지막에 for문 한번 (n) = 2nlogn + n => 대충 nlogn이라고 볼 수 있다

 

c++에서 unordered_map은 해시맵으로 구현되어있다 == find에 O(1)밖에 안든다!!

-> completion으로 해시맵 초기화 하는 반복 (n) + participant를 확인하는 반복(n) = 2n => 대충 n이라고 볼 수 있다

 

nlogn VS n 이므로... 해시맵이 더 좋다!