[프로그래머스] 완주하지 못한 선수 (해시 Lv. 1) - C++

0. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)  
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.
  

  

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

Participant	Completion	Return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

• 예제 #1 : "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
• 예제 #2 : "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
• 예제 #3 : "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• Participant 배열로는 N명의 참가자의 이름이 들어있고, Completion 배열에는 N-1명의 완주자들이 있다.
• 그 한 명을 찾으면 되는 아주 간단한 문제이다.

  

• 간단한 예시를 하나 만들어서 문제를 해결할 알고리즘을 고민해보면 생각보다 쉬운 해결책이 나온다.
• 위 예시에서는 B가 답이라는 것이 너무 쉬워서 알고리즘을 유추하기 어려울 수 있는데, 결론은 좌우를 비교해서 없는 것 하나만 찾으면 된다.
• 사람 눈으로 보고 찾는 건 너무 자연스럽지만, 이걸 프로그램으로 짜서 어떻게 컴퓨터에게 전달할 수 있을까?

1. 해결책 1 : Sorting 한 뒤에 Loop을 통해 1:1 비교를 하고, 서로 다른 항목이 나온 사람이 완주하지 못한 사람이다.
2. 해결책 2 : 그래도 명색이 해시 문제인데... 해시를 사용하는 방법이 있다.

 

 

 

 

 

3-1. 해결책 1 - Sort/Loop을 사용한 solution

• 명색이 해시 문제라 해시로 풀어야 한다는 걸 알지만, 시험에서는 유형을 정해주지 않는다는 함정이 있다.
• 난이도가 높은 문제를 Sort/Loop으로 풀려고 시도하는 건 대부분 시간 낭비인 경우가 많지만, 이 문제와 같이 간단한 문제는 Loop을 2중/3중으로 만들지 않고 1중 Loop로 만들 방법만 생각이 난다면 충분히 도전할 가치가 있다고 본다.

#include <iostream>
#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];
}

int main(void)
{
    vector<string> part = {"leo", "kiki", "eden"};
    vector<string> comp = {"eden", "kiki"};
    cout << solution(part, comp);
    return 0;
}

1) 정렬

• 사람 눈으로 보기에는 정답을 찾기가 참 쉽지만, 컴퓨터는 눈으로 볼 방법이 없으니 정렬을 해놓고 동일 index 번호끼리 비교를 해야 한다.
• 정렬을 해놓으면 다음과 같이 나온다.

위 간단 예제를 정렬하면 이렇게 나온다.

2) 1중 Loop 돌며 다른 참가자 찾기

• Completion 배열을 기준으로 잡고 처음부터 끝까지 돌면서 비교한다.
• 양쪽 배열을 다 정렬했기 때문에, 같은 index의 값이 다르다면, participant[index] 값이 정답이 될 것이다.

Index 0 : 둘이 같은 값이 아니니, 'A'는 완주한 선수가 아니다.

• 0번 Index부터 돌면서 두 배열의 값이 같은지를 비교하는 단계이다.
• 1번 Index를 비교해보면 B와 C로 서로 다르다.
• 이때 completion 배열은 완주한 사람들의 List이니 completion[1]은 정답이 될 수 없다.
• participant[1]이 완주하지 못했다고 판단된다.

3) 예외 처리 (Exception)

• 일반적인 케이스 외에도 항상 예상치 못한 경우가 나오기 마련이다.
• 이런 예외를 잘 처리하는 것이 시험에서도 중요하고 실무에서도 큰 차이를 불러온다. (좋은 프로그래머로 인정받는 것도 있고, 나의 퇴근 시간을 줄이는 Key...)
• 현재 코드는 completion을 기준으로 돌기 때문에, 완주하지 못한 선수가 participant 배열의 마지막 index에 있다면 처리가 되지 못한다. 또 하나의 간단한 예를 들어서 보자.

이렇게 시작한다고 치자

 

• 위의 예시를 그려놓고 보면 불길한 기운이 엄습한다.
• completion의 배열은 총 2개. 2개를 다 돌아봐도 완주하지 못한 선수를 찾을 방법이 없다. 
• 즉, 알파벳 순서 상 제일 뒤에 있는 선수가 완주하지 못했다면 찾을 방법이 없다.
• 이를 위해 마지막에 participant[index]를 반환하면 정답인 C를 반환할 수 있게 된다.

 

3-2. Hash를 사용한 solution

• 그래도 Hash 문제이고 개념을 이해하는 것이 중요하니 동일한 문제를 Hash로 풀어보자.
• Hash를 사용하더라도 결국 우리가 원하는 것은 Participant는 있고 Completion에는 없는 한 명을 찾는 것이다.

#include <iostream>
#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;
}

int main(void)
{
    vector<string> part = {"leo", "kiki", "eden"};
    vector<string> comp = {"eden", "kiki"};
    cout << solution(part, comp);
    return 0;
}

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 자료구조이고, C++에서는 unordered_map을 사용한다.
• unordered_map<string, int> map로 지정하면 Key는 String 형태, Value는 Integer 형태로 정의하는 것이다.
• 이 문제에서 Key는 Participant의 이름이 되겠고, Value는 Count가 되기 때문에 String/Integer로 해야 한다.

2) HashMap에 Participant 추가하기

• 'Hashing을 한다'라고도 표현하는데, HashMap에 Participant를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.
• map.insert(make_pair(player, 1)) : Hash Map에 Key와 Value를 한 쌍으로 입력하는 함수이다.
• insert가 되어있는 player에 대해서는 map[player]++ 혹은 map[player]--로 쉽게 연산할 수 있다.

• Index 0

• Index 1

• Index 2

• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Count Table을 만들어서 각 Participant의 Count를 세어 놓는다.
• 다음 단계에서는 완주한 사람들은 Value를 1씩 빼는 동작을 하고, 그러면 남아있는 한 사람이 완주하지 못한 선수가 될 것이다.

3) HashMap에서 완주한 선수 빼기

• 각 선수들의 이름이 Key로 들어가고, 그 이름을 가진 사람이 몇 명 있는지 Value로 Hash Map을 완성하였다.
• 그렇다면 이 HashMap에서 완주자들을 제외시키면, 한 명만 남게 될 것이고 그 사람이 우리가 찾는 정답일 것이다. 
• 위와 동일하게 예제를 통해서 보자.
• Index 0

• Index 1

4) Value가 0이 아닌 참가자 찾기

• 이쯤 되면 문제가 다 해결됐다고 볼 수 있다.
• 남아있는 1명이 마피아완주하지 못한 사람이니, 이제 HashMap을 한번 돌면서 Value가 0이 아닌 사람을 찾으면 된다.
• 즉, 전체 Key를 하나씩 확인해서 Value가 0이 아닌 경우 answer에 담아주는 동작을 하는 코드이다.

 

4. 참 쉽죠?

• 만약 스스로 문제를 해결하지 못해서 이 글을 보고 있다면, 다음에 비슷한 문제 유형도 풀기 어려울 것이다.
• 다음에 이런 문제를 풀기 위해서는 문제 접근 방식과 Hash 사용 방법을 익혀서, 유사한 문제를 보고 '아 Hash 쓰면 되겠는데?'라는 결과가 나올 수 있도록 연결을 시키는 것이 코딩 테스트를 통과해서 취직하는 데 핵심이라고 본다.
• 잘못된 부분, 오타, 이해가 되지 않는 부분이 있다면 댓글로 남겨주시면 같이 보고 자료를 더 개선해 나가면 좋겠다.

 

5. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.