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

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스

이 문제는 해시 카테고리에 있지만 해시를 사용하지 않고 풀 수 있기때문에

그냥 정렬을 이용해서 먼저 풀어보고 map을 이용해서도 풀어봤다.

 

문제에서 completion의 길이는 participant보다 1이 작다고 했으므로 완주하지 못한 선수는 항상 1명뿐이다. 

 

먼저 정렬을 이용한 풀이다. 

participant와 completion 벡터를 각각 정렬해준다. 그러면 완주하지 못한 선수전까지는 같은 이름이라면 같은 위치에 올 것이다.

 

completion의 길이만큼 반복문을 돌면서 participant와 이름이 같은지 확인한다.

이름이 다르다면 그떄의 선수가 완주하지 못한 선수이다.

 

participant의 마지막 선수가 완주하지 못한 선수인 경우는 flag변수를 사용해서 따로 처리해주었다.

처음에 flag를 false로 초기화 해놓는다.

위에서 반복문을 돌다가 완주하지 못한 선수를 발견하였다면 flag를 true로 바꿔준다.

 

반복문이 끝났는데도 flag가 false라면 반복문 내에서 완주하지 못한 선수를 찾지 못한 경우이다.

즉, 마지막 participant에 남은 선수가 완주하지 못한선수이다.

 

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

 

 

 

두 번째 풀이는 map을 사용하였다.

map은 key는 string으로 value는 int로 해서

string에는 선수의 이름, value에는 해당 이름을 가진 선수의 인원수로 저장한다.

 

먼저 completion에 있는 선수들을 map에 1값으로 추가한다.

동명이인이 있는 경우에는 해당 선수의 값을 증가시킨다.

 

그리고 모든 참가자들(participant)에 대해서 map에 존재하는지 확인한다.

map에 존재하지 않는다면 바로 그 선수가 완주하지 못한 선수이다.

map에 참가자가 존재한다면 값이 0인지 확인해주어야한다.

값이 0이면 이미 동명이인인 선수가 완주한 것을 나타내는 것이므로 그때의 선수가 완주하지 못한선수이다.

0이 아닌 경우에는 동명이인인 경우의 처리를 위해서 map의 값을 하나 빼준다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
 
using namespace std;
 
 
string solution(vector<string> participant, vector<string>  completion) {
    string answer = "";
    map<string, int> m;
    
    for(auto elem : completion) {
        //map에 없다면 값을 1로 주고 추가한다.
        if(m.find(elem) == m.end()) {
            m.insert(make_pair(elem, 1));
        } else {
            //map에 이미 있다면 값을 증가시킨다.
            m[elem]++;
        }
    }
    
    for(auto elem : participant) {
        //map에서 참가자를 찾지 못했다면 해당 참가자가 완주하지 못했다.
        if(m.find(elem) == m.end()) {
            answer = elem;
            break;
        } else {
            //map의 값이 0인 경우에도 해당 참가자가 완주하지 못한 경우이다.
            if(m[elem] == 0) {
                answer = elem;
                break;
            } else {
                //값을 감소시킨다.
                m[elem]--;
            }
            
        }
        
    }
    
    return answer;
}