[Programmers]-완주하지 못한 선수(해시)

문제

“코딩테스트 고득점 Kit - 해시” 문제이다.

코드

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {

        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for(i=0;i<completion.length;i++){
            if(!participant[i].equals(completion[i])) return participant[i];
        }
        return participant[i];
    }
}

코드 설명

처음에 이렇게 풀었다.

하지만 해시문제답게 해시로 푸니 더 빠르다.

코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> hm = new HashMap<>();
        
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) { 
            if (hm.get(key) != 0) return key;
        }
        return "";
    }
}

코드 설명

이렇게 해시맵을 써주면 효율성에서 4~5배 차이가 보인다.

아무래도 정렬에서 시간이 길어지는 것 같다.

이 코드는 getOrDefault가 핵심이 된다.

getOrDefault(key, defaultValue)는 해시맵에 key가 있으면 key의 value를 반환하고 없으면 defaultValue를 반환한다. 이렇게 첫for문의 key에는 이름, value에는 이름 갯수가 나타난다.

두번 째 for문에서는 중복되면 value-1 해준다.

중복이 안되면 못들어온 사람이니 찾으면 된다.

요약

• getOrDefault(key, defaultValue) : 해시맵에 key가 있으면 key의 value반환, key가 없으면 defaultValue 반환.