[Java] 프로그래머스 Hash - 완주하지 못한 선수 (Lv1)

예전에 C++로 코딩테스트 준비할 때 한 번 씩 풀어봤던 문제인데, java로 다시 기초부터 쌓기 위해 풀어본다.

프로그래머스 - 완주하지 못한 선수
https://school.programmers.co.kr/learn/courses/30/lessons/42576

완주하지 못한 선수

ArrayList를 사용한 풀이

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> participantsList = new ArrayList<>(Arrays.asList(participant));
        for(String s : completion) participantsList.remove(s);

        return participantsList.get(0);
    }
}

이렇게 풀면 안 된다!
문제만 보고 ArrayList만 사용해도 풀 수 있지않나 해서 한 번 풀어본건데 효율성 0점 나오더라..!
찾아보니 remove 할 때마다 탐색이 돌아가 효율성면이 떨어진다고...

HashMap을 사용한 풀이

import java.util.HashMap;
import java.util.Map;

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

hash map을 사용해서 풀면 정확도, 효율성 모두 100점 나온다.
참가한 선수의 이름을 key, 참가한 수를 value로 두는데 즉 동명이인이 있으면 +1씩, 없으면 1이 되는 hash map을 만든다.
그리고 완주한 선수 리스트를 for 문으로 돌면서 -1씩 하면 완주하지 못한 선수만 1 이상이 남게 된다.
(문제에 조건으로 명시되어 있지는 않지만, 완주하지 못 한 선수는 1명으로로 되어있는 듯 하다.)