[220805] Level_ 1 완주하지 못한 선수 (오답노트)

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

프로그래머스

완주하지 못한 선수가 나처럼 느껴지는 문제였다,, 효율성 검사 5개 모두 0점을 맞으며 틀려버린 문제! 이중 for문 쓸때부터 쎄하긴 했지.. 역시 아니다 싶으면 코딩에선 확실히 아니다. 구글링을 통해 찾은 방법으로 내 방법이 어디가 왜 틀린건지 정확히 분석해보겠다. 

 

 

내코드

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    vector <pair<string, int>> totalAthlete;
    sort(participant.begin(), participant.end());
    int index = -1;
    for (int i = 0; i < participant.size(); i++)
    {
        if (i > 0 && participant[i] == participant[i - 1]) totalAthlete[index].second++;
        else
        {
            totalAthlete.push_back(make_pair(participant[i], 1));
            index++;
        }
    }
    for (int i = 0; i < completion.size(); i++)
    {
        for (int k = 0; k < totalAthlete.size(); k++)
        {
            if (totalAthlete[k].first == completion[i])
            {
                totalAthlete[k].second -= 1;
                break;
            }
        }
    }
    for (int i = 0; i < totalAthlete.size(); i++) if (totalAthlete[i].second == 1) return totalAthlete[i].first;
    return answer;
}

1. 첫번째 for문 : 참가자의 사이즈만큼 반복문을 돌려서 이전 사람과 같으면 미리 만들어놓은 명단에 push_back하지 않고 second값만 ++해준다. (동명이인 예외 제거) 그리고 같지 않다면 미리 만들어놓은 명단에 push_back해준다. second값은 1로 지정한다. 

2. 두번째 for문: 이중 for문을 돌려 명단의 이름과 완주자의 이름이 같으면 해당 명단의 second값을 하나 줄여준다. 

3. 세번째 for문: 명단을 쭉 검사해서 second값이 1이면  아직 통과하지 못했단 소리니까 그 이름을 return 한다. 

 

 

 

정답코드 1. Loop와 Sort를 이용한 방법(해쉬x)

#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());
    int i = 0;
    for (; i < completion.size(); i++)
        if (participant[i] != completion[i])
            break;
    return participant[i];
}
출처: https://coding-grandpa.tistory.com/89 [개발자로 취직하기:티스토리]

 생각을 더 단순하게 했어야 한다. sort를 쓸 생각은 했지만 난 인자의 두 배열을 비교할 생각은 하지 못했고, sort를 해서 이전 순서 선수와 비교해서 같으면 동명이인이니까 추가하지말고 value값에 ++만 해주자는 식으로 생각했다. 저렇게 풀면 너무나도 간단한 문제다. 

 

 

 

 

정답코드 2. 문제의 의도대로 해쉬(unorderd_map)를 이용한 방법

#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;
    for (auto player : participant)
    {
        if (map.end() == map.find(player))
            map.insert(make_pair(player, 1));
        else
            map[player]++;
    }

    for (auto player : completion)
        map[player]--;

    for(auto player : participant)
        if (map[player] > 0)
        {
            answer = player;
            break;
        }
    return answer;
}
출처: https://coding-grandpa.tistory.com/89 [개발자로 취직하기:티스토리]

1. 나는 vector배열에 pair로 넣은 반면에 이 코드에선 해쉬를 사용했다.

2. for문을 참가자 배열만큼 돌려 만약 만들어놓은 해쉬에 참가자 이름이 없으면 insert로 만들어준다. 이름이 있다면 해당 해쉬의 value값에 ++해준다. (내방법과 비슷!)

3. for문을 완주자 배열만큼 돌려 해쉬에서 빼준다. 애초에 난 map의 key값을 인덱스처럼 써서 접근할 수 있는지 조차 몰랐음.. 그렇기에 난 이중 for문을 돌려야 했다..

4. for문을 참가자 수 만큼 돌려 해쉬에서 아직 1이 남아있는(결승선을 통과하지 못한) 한명을 찾아낸다. 

 

 

 

 

느낀점

사실 첫번째 방법은 생각치도 못한 참신한 방법이라 난 언제쯤 저런 쉽고 똑똑한 풀이법을 스스로 생각해낼 수 있을까 고민하게 만들었다. 그런데 해쉬를 사용했던 두번째 방법을 보고 조금 자신감이 생겼다. 결국 나와 똑같은 풀이를 생각했지만 무엇을 사용했느냐에 따라 효율성에서 갈린거였다. 모르는건 지금처럼 코테를 많이 풀어보며 배우면 되니까!!! 열심히 풀어보자. 그리고 배운건 꼭 적어놓도록 하자,, 그리고 지금처럼 답을 보고 푼 문제는 꼭 나중에 다시 풀어보기!!!!!!