Programmers Lv1) 완주하지 못한 선수

Programmers Lv1) 완주하지 못한 선수

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습/해시에 수록된 문제로, 프로그래머스의 레벨1에 해당하는 문제입니다. 또한 문제는 C++로 풀이되었습니다

문제 풀이

• 문제해서 해겷해야 하는 요점은 아래와 같습니다.

  1. 참가자 중 완주하지 못한 사람을 찾아낼 것
  2. 단 참가자는 동명이인이 존재할 수 있음 (중복이 존재할 수 있음)

1. 참가자 중 완주하지 못한 사람을 찾아낼 것

• 참가하지 못한 사람의 경우 다양한 방법으로 찾아낼 수 있겠지만, 여기서는 중복의 문제 등도 있기 때문에 string, 즉 사람의 이름을 key 값으로 가지고 int를 value로 가지는 map을 사용하였습니다.
• completion vector에 들어있는 모든 완주자들을 key로 가지는 value의 값을 1씩 더해주고, participant vector에 들어있는 모든 참가자들을 key로 가지는 value의 값을 1씩 감소합니다. 이후 value의 값을 통해서 완주하지 못한 사람을 찾을 수 있습니다.

2. 참가자는 동명이인이 존재할 수 있음

• 동명이인의 문제는 map의 value와 key로 해결할 수 있습니다. 동명이인의 경우 같은 key값을 가지게 됩니다. A와 A가 존재하고 이들 중 한 명만 완주하였다면 value의 값은 최종적으로 -1이 됩니다.
• 만약 value의 값이 음수라면 key값을 이름으로 가지는 참가자가 완주를 하지 못했다는 의미가 되기 때문에, value가 음수인 key값을 리턴하면 문제를 쉽게 해결할 수 있습니다.

핵심 풀이법

• 이 문제에서 사용된 std의 특성 중 1개로, map의 value를 초기화 하지 않는 경우 0으로 자동 초기화가 이루어집니다. 이를 활용하였습니다.
• 또한 해싱을 풀이하는 방법에는 여러 가지가 있는데, 만약 key와 value로 나눌 수 있는 경우 map을 활용해서 해싱을 진행하면 보다 편리하게 해싱이 가능합니다.

전체 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> m;
    for (auto temp : completion) m[temp] += 1;
    for (auto temp : participant) {
        m[temp] -= 1;
        if(m[temp] <0 ) return temp;
    }
}

위 문제의 경우 프로그래머스 완주하지 못한 선수 / C++ (map) 를 참고하여 풀이하였습니다.