[프로그래머스 코딩테스트 고득점 Kit - 해시] 완주하지 못한 선수

해시 문제

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

 

 

---

[문제 풀이]

 

두 집합의 차집합을 구하는 문제입니다.

집합에서 중복을 허용했으므로 set이 아닌 map을 사용하였습니다.

 

map의 key로 문자열을, value로 동명이인의 수를 기록합니다.

그리고 completion에서 명단을 하나씩 확인하면서 map의 value를 1씩 줄여나갑니다.

value가 1이었던 경우 map에서 삭제합니다.

 

두 집합의 크기 차이가 1이었으므로 위의 과정을 완료하면 map에는 하나의 값만 남게 되고 그 값의 key(string)를 출력하면 해결이 가능합니다.

 

c++의 map은 레드블랙트리 기반이므로 삽입, 삭제, 탐색 모두 $O(logn)$의 시간 복잡도를 갖습니다.

Java의 HashMap은 key를 해싱하므로 삽입, 삭제, 탐색 모두 $O(1)$의 시간 복잡도를 갖습니다.

명단의 크기 N의 최대가 100,000이므로 시간 안에 위의 과정을 처리할 수 있습니다.

 

c++에 내장된 차집합을 구하는 함수인 set_difference의 아이디어를 빌려 두 벡터를 정렬한 후 비교하여 답을 도출하는 풀이도 있습니다.

 

정렬의 시간 복잡도 역시 $O(NlogN)$이므로 시간 복잡도는 같습니다.

 

---

[소스 코드] / C++

 

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    int N = participant.size();
    map<string, int> hashing;
    
    for (int i = 0; i < N; i++) {
        string s = participant[i];
        if (!hashing.insert(make_pair(s, 1)).second) {
            hashing[s]++;
        }
    }
    
    for (int i = 0; i < N - 1; i++) {
        string s = completion[i];
        if (hashing[s] > 1) hashing[s]--;
        else hashing.erase(s);
    }
    
    string answer = hashing.begin()->first;
    return answer;
}

 

---

[메모]

 

• iterator는 포인터처럼 사용이 가능하다. 포인터는 아니다.
• map의 find 함수는 iterator를 반환한다. 찾지 못하면 end()를 반환한다.
• map의 insert 함수는 반환값이 있다. pair를 반환하는데 first는 iterator, second는 bool이다. bool은 중복 체크
• map의 erase 함수는 iterator를 사용한 범위 혹은 특정 값, key값을 사용한 특정 값 등을 지울 수 있다.