[Algorithm] 문제풀이 - 해시-2

1. 완주하지 못한 선수

• 수많은 마라톤 선수들이 마라톤에 참여하였습니다.
• 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

주어지는 것

• 마라톤에 참여한 선수들의 이름이 담긴 배열 participant
• 완주한 선수들의 이름이 담긴 배열 completion

반환해야할 것

완주하지 못한 선수의 이름

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

participant	completion	isCompleted	i	j	participant[i] == completion[j]	isCompleted	return
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	[false, false, false]	0	0	false
			0	1	false
			0	2	true	[false, false, true]
			1	0	true	[true, false, true]
			2	0	false
			2	1	false
			2	2	false, (isCompleted ≠ false)		participant[2]

brute force

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        boolean[] isCompleted = new boolean[completion.length];
        
        for (int i = 0; i < participant.length; i++) {
            String part = participant[i];
            boolean isComp = false;
            for (int j = 0; j < completion.length; j++) {
                if (completion[j].equals(part) && isCompleted[j] != true) {
                    isCompleted[j] = true;
                    isComp = true;
                    break;
                }
            }
            if (!isComp) return participant[i];
        }
        return answer;    
    }
}

hash

participant	completion	HashSet	i	hashSet.contains(participant[i]) ?	HashSet	return
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	[“stanko”, “ana”, “mislav”]	0 (mislav)	hashSet.remove(participant[i])	[“stanko”, “ana”]
[“mislav”, “stanko”, “mislav”, “ana”, “mislav”]	[“stanko”, “ana”, “mislav”, “mislav”]
→ hashSet(“stanko”, “ana”, “mislav”)		1 (stanko)	hashSet.remove(participant[i])	[“ana”]
			2 (mislav)	X		“mislav”

// 효율성 실패
public class Marathon {

    public static void main(String[] args) {
        Marathon m = new Marathon();
        String s = m.solution(new String[] {"mislav", "stanko", "mislav", "ana"}, new String[] {"stanko", "ana", "mislav"});
        System.out.println(s); // mislav

        s = m.solution(new String[] {"marina", "josipa", "nikola", "vinko", "filipa"}, new String[] {"josipa", "filipa", "marina", "nikola"});
        System.out.println(s); // vinko
    }

    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> participantMap = toMap(participant);
        Map<String, Integer> completionMap = toMap(completion);

        for (String name: participantMap.keySet()) {
            if (completionMap.getOrDefault(name, 0) != participantMap.get(name)) {
                return name;
            }
        }
        return null;
    }

    private Map<String, Integer> toMap(String[] participant) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : participant) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        return map;
    }
}