Solution

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> map = new HashMap<>();
        
        for (String c : completion) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        for (String p : participant) {
            int cnt = map.getOrDefault(p, 0);
            if (cnt == 0) {
                answer = p;
                break;
            }
            map.put(p, cnt - 1);
        }
        
        return answer;
    }
}

HashMap을 활용하여 시간복잡도 O(n)으로 해결하는 문제이다. 참가자와 완주자는 1명을 제외하곤 동일한 사람들의 집합이므로, 완주자들을 HashMap에 먼저 넣고, 참가자 이름으로 HashMap에서 값을 찾는다. 특수 케이스로 “동명이인” 조건이 있는데, 이는 HashMap의 value를 각 이름의 수를 사용하는 것으로 해결한다. 참가자 기준으로 HashMap에서 찾은 값이 0 이면 해당 참가자는 완주하지 못한 것이며, 그렇지 않은 경우 value를 하나씩 줄이면 동명이인 케이스를 포함하여 완주하지 못한 참가자를 찾을 수 있다.

getOrDefault()

문서: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#getOrDefault-java.lang.Object-V-

getOrDefault()는 Map에서 키를 조회할 때, 없으면 내가 지정한 기본값을 대신 돌려주는 메서드이며, Java8부터 도입되었다. 기본적인 형태는 아래와 같다.

V getOrDefault(Object key, V defaultValue)

  • key: 찾을 키

  • defaultValue: 키에 해당하는 값이 없을 때 리턴 할 default 값

HashMap

주요 메서드

메서드설명반환값사용 예시
put(K key, V value)값 추가 / 기존 값 덮어쓰기이전 값 (없으면 null)map.put("a", 1);
get(Object key)키에 해당하는 값 조회값 (없으면 null)map.get("a");
getOrDefault(Object key, V defaultValue)값 없을 때 기본값 반환값 또는 defaultmap.getOrDefault("a", 0);
containsKey(Object key)키 존재 여부booleanmap.containsKey("a");
containsValue(Object value)값 존재 여부booleanmap.containsValue(1);
remove(Object key)키 삭제삭제된 값map.remove("a");
putIfAbsent(K key, V value)키 없을 때만 추가기존 값 or nullmap.putIfAbsent("a", 1);
replace(K key, V value)값 교체 (키 있어야 함)이전 값 or nullmap.replace("a", 2);
replace(K key, V oldVal, V newVal)값이 oldVal일 때만 교체성공 여부map.replace("a", 1, 2);
size()크기intmap.size();
isEmpty()비어있는지 확인booleanmap.isEmpty();
clear()전체 삭제voidmap.clear();

순회 관련 메서드

메서드설명예시
keySet()key 목록 조회for (K k : map.keySet())
values()value 목록 조회for (V v : map.values())
entrySet()key+value 함께 조회 (추천)for (Map.Entry<K,V> e : map.entrySet())