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

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42576

 

순서가 상관이 없으므로 unordered_map을 사용하였습니다.

unordered_map은 비정렬 연관컨테이너로, 중복을 허용하지 않고 map과 달리 key를 기준으로 자동정렬하지 않습니다.

 

unordered_map과 map, hash_map 등의 개념을 다른 포스팅으로 정리했습니다.

맨 아래에 첨부한 링크를 참고해 주세요.

 

 

이제 문제를 살펴볼게요.

 

마라톤 경기에 참여한 선수의 수인 participant가 있고, 그보다 1 작은 크기의 completion 벡터에는 완주한 선수가 담겨있으니, 완주하지 못한 선수는 전체에서 1명입니다.

 

여기서 포인트는 '마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하'라는 점입니다.

 

범위가 이렇게 큰 경우엔 벡터나 배열 같은 순차 컨테이너로 모든 원소를 순회하면 시간이 초과됩니다.

따라서, 이분탐색이나 해시처럼 시간복잡도가 작은 방법을 생각해야 하는 문제입니다.

 

[주석 없는 코드]

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map <string,int>umap;
    for(string name : participant)
        umap[name]++;
    for(string name : completion)
        umap[name]--;
    for(string name : participant){
        if(umap[name]==1)
            answer = name;
    }
    return answer;
}

 

[주석 있는 코드]

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map <string,int>umap;
    //참여한 사람 모두 value가 1
    for(string name : participant)
        umap[name]++;
    //완주한 사람은 value가 0
    for(string name : completion)
        umap[name]--;
    //value가 1인, 즉 완주하지 못한 사람을 찾기
    for(string name : participant){
        if(umap[name]==1)
            answer = name;
    }
    return answer;
}

 

unordered_map은 umap[name]++만 해도 사용이 가능합니다.

기존에 없는 key에 대한 코드가 들어오면 자동으로 type에 맞춰 value를 초기화합니다.

지금 문제에서처럼 umap[name]++; 과 같은 연산뿐만 아니라 if문 내의 umap[name]==1 과 같은 조건문에서도 없는 key에 대한 코드가 들어오면 자동으로 초기화합니다.

따라서 없는 key라고 할지라도 저런 코드에서 에러가 안 나요.

 

따라서 key의 존재여부를 확인하려면, 위와 같이 umap이라는 unordered_map이 있다고 가정할 때

if(umap.end() == umap.find(key))를 하면 됩니다.

find함수는 해당 키가 없으면 iterator인 umap.end()의 값을 리턴하고, 있으면 해당 key가 담긴 iterator를 리턴합니다.

 

 

[STL개념과 컨테이너 종류] - https://eocoding.tistory.com/5

STL 개념과 컨테이너 종류

[hash_map, unordered_map,map 비교와 특징 정리] - https://eocoding.tistory.com/6

hash_map, unordered_map, map 비교, 특징 정리 - C++