AlgorithmProgrammers

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

, ,

1. 문제 링크

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

2. 문제 조건

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

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

3. 컴퓨팅 사고

이 문제에 있어서 가장 중요했던 점은 hashmap을 사용할 수 있는지 여부를 확인하는 문제였습니다. 참가자와 완주자의 명단이 주어졌을때 완주자의 명단을 Key, 완주자의 등장횟수를 Value로 두면 쉽게 풀 수 있습니다.

완주자의 명단을 HashMap에 저장하기
완주자의 명단을 HashMap에 저장합니다. 예를 들면, 참가자[leo, kiki, eden] 완주자 [eden, kiki]의 값이 주어졌다고 생각을 하겠습니다. 완주자 <eden, 1>, <kiki,1>의 값으로 저장시킵니다.

참가자의 명단에서 참가했지만 완주하지 못한 선수 찾아내기
완주한 명단 즉, 완주한 사람의 이름 Key값이 참가자의 명단에 없을 경우 그 사람은 참가는 했지만 완주하지 못한 경우가 됩니다.

동명이인 찾아내기
레오가 두명이 등장하는 참가자 [leo, leo, kiki, eden] 완주자[leo, eden, kiki] 라고 가정하겠습니다. 레오 같은 경우는 완주자의 명단에는 한명이 존재하고 참가자의 명단에는 두명이 존재하게됩니다. 즉, 완주자 1명, 참가자 2명이기때문에 레오의 동명이인이 참가자이지만 완주자의 명단에 오르지 못했다는것을 알 수 있습니다.

이것을 소스코드로 어떻게 표현했을까요
? leo의 키값을 찾은 후에 leo의 등장하면 현재 Hashmap 즉, 완주자 명단에 있는 value의 값을 가져오게 됩니다. 그중에서 leo라는 값이 두번등장하게 되면 음수값이 되므로 결국 leo는 동명이인이며 2명중 1명만 참가하는것이 됩니다.

4. 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String,Integer> m = new HashMap<>();
        String answer = "";
        for(int i=0; i<completion.length; i++){
            if(!m.containsKey(completion[i])){
                m.put(completion[i],1);
            }else {
                int tmp = m.get(completion[i]);
                m.put(completion[i], tmp+1);
            }
        }

        for(int i=0; i<participant.length; i++){
            // 완주자와 참가명단에서 못찾았으면
            if(!m.containsKey(participant[i])){
                answer = participant[i];
            }else {
                // 동명이인일 경우 값을 하나씩 줄였을때 0보다 작으면 그 사람이 완주자, 동명이인 체크해주기
                int tmp = m.get(participant[i]);
                m.put(participant[i],tmp-1);
                if(m.get(participant[i])< 0){
                    answer = participant[i];
                }
            }
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <string>
#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
     map<string,int> m;
    for(int i=0; i<completion.size(); i++){
        // 완주자 없는 경우
        if(m.find(completion[i]) == m.end()){
            m.insert(make_pair(completion[i], 1));
        }
        // 완주자 있는 경우
        else {
            // 완주자 수 카운팅
            m[completion[i]]++;
        }
    }
    for(int i=0; i<participant.size(); i++){
        // 완주자와 참가자 명단에서 못찾았을 경우
        if(m.find(participant[i]) == m.end()){
            answer = participant[i];        // 못찾은 사람이 정답
            break;
        }
        // 동명이인일 경우 값을 하나씩 줄였을때 0보다 작으면 그 사람이 완주자, 동명이인 체크해주기
        else {
            m[participant[i]]--;
            if(m[participant[i]] < 0){
                answer = participant[i];
                break;
            }
        }       
    }
    return answer;
}
Share