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

1) 문제

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

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

참가자 배열과 완주한 선수들의 배열 두 배열이 주어지고 완주하지 못한 선수들을 return해야한다.

문제 자체는 매우 간단하다. 하지만 hash를 사용해서 풀어야 하는 문제

나는 자료구조 쪽 지식이 매우 부족하기 때문에 level1 문제부터 시작했다.

Hash에 대한 개념적인 정리는 따로 포스팅을 해야겠다.

실제 시험에서도 가능한지는 잘 모르겠으나 프로그래머스에서는 unordered_map의 사용이 가능한 것 같다. 

 

2) 풀이

일단 알고리즘 자체는 매우 간단하다.

1. sorting해서 두 배열을 비교한다. - 하지만 이 경우 map을 사용할 필요가 없다.

2. map<stirng, int>를 선언해서 선수들의 이름을 key값으로 이용한다.

이 경우 완주한 선수의 map value를 1 증가시키고 참가한 선수의 map value를 1 감소시킨다.

완주하지 못한 선수는 value가 1이기 때문에 1인 선수만 출력한다.

일단 hash를 사용해야 하기 때문에 2번 solution으로 진행했다.

 

hash를 직접 구현해보는 연습은 다른 포스팅에서 해보려고 한다.

 

3) 코드

string solution(vector<string> participant, vector<string> completion) {
    int answer;
    //hash map<이름, 카운트>
    unordered_map<string, int> hash;
    for(string name:completion) {
        hash[name] += 1;
    }
    for(string name:participant) {
        hash[name] -= 1;
        if(hash[name] < 0) {
            return name;
        }
    }
}

 

4) 정리

내가 hash에 대해 완벽히 알고 있지 않고 stl에서 제공하는 map도 단순 입력 출력 외에는 잘 모른다는 것이 문제다.

추후에 hash를 직접 구현해보고 stl이 어떻게 구현되어있는지 공부할 필요가 있다.

문제 관련해서는 처음에 참가자 벡터에서 1을 더하고 완주자 벡터에서 1을 빼는 방식으로 구현했다가 잠깐 헤맸다.

당연한 소리지만 완주자 벡터를 나중에 확인하는 경우 완주하지 못한 사람을 거를 수 없다.

아무리 간단해보이는 문제라도 좀 더 구체적으로 solution을 세울 필요가 있겠다.