2019. 12. 28. 10:08ㆍ알고리즘/프로그래머스
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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이라서 쉬운문제인줄 알았다. 단 한명의 선수를 제외하고 모두 완주하였기에 답은 문자열 딱 한개였다.
그래서 단순히 participant백터에서 completion백터에 없는것을 찾으면 될꺼라고 생각했다.
2중 for문을 돌려서 모조리 다 비교해보고 있는것을 모조리 삭제하면 나머지 남은게 답이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <string>
#include <vector>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
for(int i=0; i<participant.size(); ++i){
for(int j=0; j<completion.size(); ++j){
if(participant[i] == completion[j]){
participant.erase(participant.begin() + i);
break;
}
}
}
string answer = participant.back();
return answer;
}
|
이렇게 돌리고 나니 효율성 문제에서 죄다 실패했다.
생각은 했었지만 레벨1부터 효율성을 보는지 몰랐다. 그래서 좀 더 고민을 해보았다.
- 두번째 방법(성공)
다른사람들의 방법을 조금씩 찾아보고 힌트를 얻었다. 두 백터를 모두 정렬한다면 모조리 비교할 필요없이 한번의 반복문으로 비교를 쭉 하다가 처음으로 다른부분이 바로 완주하지 못한 사람이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
sort(participant.begin(),participant.end());
sort(completion.begin(),completion.end());
string answer;
for(int i=0; i<participant.size(); ++i){
if(participant[i] != completion[i]){
answer = participant[i];
break;
}
}
return answer;
}
|
sort를 쓴다는것도 어떻게 보면 효율성을 떨어뜨리는 일이기때문에 효율성 테스트가 통과될까 싶었는데 잘 통과했다.
그런데 문제는 해시문제인데 해시를 전혀 안썼다는 문제이다. 그래서 해시를 쓰기위해 해시를 공부하고 적용해봐야겠다.
- 세번째 방법(실패)
C++에서 해시를 쓰는 STL인 unordered_set, unordered_map에 대해 공부하였다. 먼저 unordered_set을 선택하여 문제를 풀어보았다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
unordered_set<string> hash;
for(int i=0; i<completion.size(); ++i){
// 동명이인 insert 실패
hash.insert(completion[i]);
}
string answer;
for(int i=0; i<participant.size(); ++i){
if(hash.find(participant[i]) == hash.end()){
answer = participant[i];
break;
}
}
return answer;
}
|
그런데 테스트 결과가 실패했다. 원인은 중복으로 들어오는 동명이인의 경우를 생각하지 않았던 것이다. unordered_set의 경우 동일한 데이터가 들어왔을때 무시한다. 그래서 동명이인이 있을경우 동명이인중 한사람이 통과하지 못했을때 판단할 수가 없었다.
- 네번째 방법(성공)
unordered_map도 마찬가지지만 key가 같을때 즉 동명이인일때 value에 동명이인의 수를 올려주면 된다.
|
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
|
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
unordered_map<string, int> hash;
for(int i=0; i<completion.size(); ++i){
if(hash.find(completion[i]) == hash.end()){
hash.insert(make_pair(completion[i], 1));
}
else{
// 동명이인일때 value값 +1
hash[completion[i]]++;
}
}
string answer;
for(int i=0; i<participant.size(); ++i){
if(hash.find(participant[i]) == hash.end()){
answer = participant[i];
break;
}
else{
// 동명이인이 통과자 목록에 없는경우 정답
if(hash[participant[i]] == 0){
answer = participant[i];
break;
}
// 동명이인이 통과한 경우 value값 -1
hash[participant[i]]--;
}
}
return answer;
}
|
보완할점
- set, map과 같은 연관컨테이너 STL 학습
- 해쉬 알고리즘 학습
- 효율성은 아무리 쉬운 문제라도 항상 생각할 것