📌 문제

Lv1. 완주하지 못한 선수

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

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

✔️ 제한사항

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

✏️ 입출력

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

💡 코드

✅ 선수들의 이름을 담은 두 배열을 Arrays.sort를 통해 정렬하면, 모든 선수들의 이름이 사전 순으로 정렬된다. 이때, completion은 participant의 선수들 중 한 명만 빠진 형태이므로, 두 배열의 같은 인덱스의 요소를 비교했을 때 값이 다르면 해당 선수가 completion에 없다는 뜻이므로 participant[i]를 리턴하고 종료한다. 만약, 반복문을 모두 돌았다면 정렬 순서 상 가장 마지막 선수가 완주하지 못한 것이므로 paricipant의 마지막 요소를 리턴한다.

모든 테스트 케이스와 효율성을 통과하긴 했지만,, 뭔가 찝찝한 효율성 실행 시간,,

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i=0;i<completion.length;i++) {
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        } 
        
        return participant[participant.length-1];
    }
}

✅ 문제 분류가 애초에 해시였기 때문에 HashMap을 사용해서도 풀어보았다! 동명이인이 있을 수 있으므로 <이름, 인원> 형태로 맵 runner를 생성하여 participant에 있는 모든 선수들의 이름을 넣어주었다. 동명이인의 경우, 키인 이름의 값이 같으면 뒤에 넣은 값으로 덮어지므로 getOrDefalt를 사용하여 이름에 해당하는 값이 있으면 그 값에 +1, 없으면 0+1을 해서 넣어준다.

참가한 선수들의 이름을 다 넣어줬다면, 이제는 runner에서 completion에 해당하는 완주한 선수들의 값을 -1하여 0으로 만들어 줄 것이다. 이 때도 역시 getOrDefault를 사용하여 기존의 선수의 값에 계산을 수행해야 한다.

해당 작업까지 마쳤다면 마지막으로 완주하지 못한 선수의 이름을 출력해야 한다. keySet()을 통해 runner의 이름들을 리스트로 추출해서, 이름에 해당하는 값이 1이라면 완주하지 못했다는 뜻이므로 해당 선수의 이름을 리턴하고 종료한다.

확실히 정렬을 수행하지 않으니 시간이 1/3 수준으로 줄었다..

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        
        Map<String, Integer> runner = new HashMap<>();
        for(String name : participant) {
            runner.put(name, runner.getOrDefault(name, 0)+1);
        }
        
        for(String name : completion) {
            runner.put(name, runner.getOrDefault(name, 1)-1);
        }
        
        for(String name : runner.keySet()) {
            if(runner.get(name) == 1) return name;
        }
        return "";
    }
}