[프로그래머스 Lv.1 / C++] Day60. 완주하지 못한 선수

2024. 08. 02 - 코딩테스트 스터디 Day60

 
 

01. 문제 설명

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

 
 

02. 제한사항

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

 
 

03. 입출력 예

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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

04-1. 풀이 및 답 - 정렬

#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 = 0; i < completion.size(); i++) {
        if (participant[i] != completion[i]) {
            break;
        }
    }
    answer = participant[i];
    
    return answer;
}

participant와 completion을 정렬한다.
completion의 사이즈만큼 반복문을 돌면서 participant와 completion의 같은 위치에 다른 값이 있는 경우 break 하여 반복문을 빠져나오게 한다. 그 뒤, answer에 participant의 해당 위치의 값을 저장한다.
 
i를 반복문 밖에서 선언해 줘야 아래와 같은 테스트 케이스가 주어져도 답이 제대로 나온다.

participant	completion
["a", "a", "a"]	["a", "a"]

 
 

정답!
 

04-2. 풀이 및 답 - 해시

문제가 '해시' 카테고리로 분류되어 있기 때문에 해시를 사용한 풀이도 해봤다.
 

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

unordered_map으로 <string, int> 형의 해시맵을 선언해 준다.
 
participant의 모든 값을 확인하면서 map에 존재하지 않는다면, participant의 값을 key값으로, 1을 value 값으로 둔다.
map에 해당 값이 key값으로 존재한다면 value 값에 1을 더해준다.
 
completion의 모든 값을 확인하면서 map에 key 값으로 존재한다면 value 값에서 1을 빼준다.
 
participant의 모든 값을 확인하면서 map에서 해당 값을 key 값으로 가지는 value 값이 0이 아닌 값을 answer로 저장한다.
 
 

역시 정답!
 

---

끝
 

---

 
참고한 게시글

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