완주하지 못한 선수(JAVA)

1. 문제

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

 

2. 제한

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

completion의 길이는 participant의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

참가자 중에는 동명이인이 있을 수 있습니다.

 

3. 정답

import java.util.HashMap;

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

4. 설명

4-1. 해시맵 result를 만든다.

4-2. participant배열의 길이만큼 for문을 돌리면서 참여자 명단을 'key'값으로 하고 result의 'key'값에 해당되는 value값이 기존에 존재한다면 그 값에 1을 더하고 기존에 존재하지 않는 새로운 'key'값이라면 0에 1을 더하여 value값으로 넣어준다.

4-3. 예를 들어 기존에 "smith"가 'key'값으로 result에 있다면 그 'key'에 해당되는 value값에 1을 더하여 넣어주는 것이고 만일 "smith"라는 'key'값이 없어 처음보는 것이라면 새로운 'key'에 대하여 value값을 1로 넣어주는 것이다. 즉, 같은 이름의 참가자가 2명이라면 그 이름에 대한 value값도 2일 것이고 한명밖에 없다면 value값은 1인 것이다.

4-4. 다음으로 completion배열의 길이만큼 for문을 돌리면서 완주자 명단에 해당되는 사람이 기존의 result의 'key'값에 존재한다면 해당 'key'의 value값을 1을 줄여줍니다. 예를들어 참가자로 "smith"가 2명인데 완주자가 1명이라면 "smith"의 value값은 1이 될 것이다.

4-5. 위 절차들을 거치고 난 뒤에 'key'의 value 값들은 단 하나를 제외하고는 전부 0이 되어있을 것이다. 그 단 하나가 바로 완주하지 못한 사람일 것이다. 그 사람을 return한다.

 

5. 참고

5-1. 해시맵이라는 것을 처음 써봤다. 해시맵은 메모리상 구조가 'key'에는 해싱된 'key'값들이 들어가 있고 이 해싱된 값들은 각자의 value를 가르키는 주소값이라고 한다. 이에 따라 한번 저장한 뒤에 그 값을 불러오거나 수정할 때는 속도가 빠르다는 장점이 있다. 왜냐하면 삽입, 삭제시에 그 자리를 다른 데이터로 채우는 것이 아니라 value 값을 가르키고 있는 'key'값만  가볍게 바꿔주면 되기 때문이다. 해싱이 되었기 때문에 보안상 유리하다. 또한 중복값을 저장할 필요가 없어진다. 하지만 순서를 표현할 수는 없기 때문에 순서가 중요하다면 중복값으로 공간이 낭비되더라도 배열을 사용하자.

5-2. 해시맵에 대해서 더 구체적으로 확인하려면 https://passing-lane99.tistory.com/28 을 참조하자