문제

Programmers, 완주하지 못한 선수

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 마라톤 경기에 참여한 선수 중 완주하지 못한 선수를 구하는 문제이다. 마라톤 경기에 참여한 사람들을 해시 자료구조에 저장한 뒤 완주한 사람을 제거하면 참여한 선수 중 완주 하지 못한 사람이 남는다.
• C++에선 unordered_multiset을 사용하고, java에선 multiset이 없으므로 HashMap으로 multiset을 유사하게 구현하여 사용한다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_multiset<string> s;
    for (auto e : participant)
        s.insert(e);
    for (auto e : completion)
        s.erase(s.find(e));
    for (auto e : s)
        answer += e;
    return answer;
}

Java

import java.io.*;
import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> ms = new HashMap<>();
        for (var e : participant)
            ms.put(e, ms.getOrDefault(e, 0) + 1);
        for (var e : completion) {
            if (ms.put(e, ms.get(e) - 1) == 1)
                ms.remove(e);
        }
        String ans = "";
        for (var e : ms.entrySet())
            ans += e.getKey();
        return ans;
    }
}