프로그래머스 - 완주하지 못한 선수[java]

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

문제 설명

participant

["leo", "kiki", "eden"]

completion

["eden", "kiki"]

return

"leo"

이런식으로 참가자, 완료자 형태로 입력값이 오면 완료하지 못한 사람을 찾아서 return 하면 된다.

주의사항: 중복이름이 있을 수 있고 중복 이름 중 한명이 완주 하지 못할 수 있다.

문제 풀이

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> hs = new HashMap<String, Integer>();
        for(String runner : participant) 
            hs.put(runner, hs.getOrDefault(runner, 0) + 1);
        for(String runner : completion)
            hs.put(runner, hs.get(runner) - 1);
        for(String k : hs.keySet()) {
            if(hs.get(k) != 0)
                answer = k;
        }
        return answer;
    }
}

nested loop으로도 찾을 수 있지만 시간복잡도를 고려해 HashMap으로 구현을 했다.
getOrDefault()라는 유용한 메소드를 이용하였다.

getOrDefault(Key, default value) 함수는 Map안에 Key 가 있으면 불러오고 아니면 default value로 입력한 값을 가져오는 함수 이다.

nested loop을 구현했으면 O(n^2)는 나왔을 시간 복잡도를 해쉬맵을 사용하여 O(n)으로 줄였다.