exp_blog

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

participantcompletionreturn

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

##시간복잡도를 줄이기 위해 hashMap을 사용하여야 한다

-> HashMap은 Map을 구현한다. Key와 value를 묶어 하나의 entry로 저장한다는 특징을 갖는다. 그리고 hashing을 사용하기 때문에 많은양의 데이터를 검색하는데 뛰어난 성능을 보인다.

• Map 인터페이스의 한 종류로 ( "Key", value) 로 이뤄져 있다.
• key 값을 중복이 불가능 하고 value는 중복이 가능. value에 null값도 사용 가능하다.
• 멀티쓰레드에서 동시에 HashMap을 건드려 Key - value값을 사용하면 문제가 될 수 있다. 멀티쓰레드에서는 HashTable을 쓴다

. HashMap 생성자 / 메서드

출처: https://vaert.tistory.com/107 [Vaert Street]

<hash 사용>

import java.util.*; 
  
class Solution { 
    public String solution(String[] participant, String[] completion) { 
        Map<String, Integer> hash = new HashMap<>(); 
        for (String arg : participant) hash.put(arg, hash.getOrDefault(arg, 0) + 1); 
//getOrDefault를 넣어주지 않으면 중복 체크가 되지 않음 , HashMap의 put은 key가 존재하면 value를 새로운 값으로 바꿔주니까 / 이미 등록된 동명이인이 있다면 hm.getOrDefault로 인해서 2라는 값이 들어감

        for (String arg : completion) hash.put(arg, hash.get(arg) - 1); 
  
        for (String key : hash.keySet()) { 
            if (hash.get(key) != 0) return key; 
        } 
  
        return null; 
    } 
}

<다른 사람 답>

import java.util.*; 
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]; 
    } 
}